結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2019-09-26 19:29:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 1,566 bytes |
コンパイル時間 | 2,280 ms |
コンパイル使用メモリ | 201,484 KB |
最終ジャッジ日時 | 2025-01-07 19:12:11 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using i64 = long long;constexpr int size = 1 << 17;int dat[size * 2 - 1], lazy[size * 2 - 1];void propagate(int k) {if (!lazy[k]) return;if (k < size - 1) {lazy[2 * k + 1] = std::max(lazy[2 * k + 1], lazy[k]);lazy[2 * k + 2] = std::max(lazy[2 * k + 2], lazy[k]);}dat[k] = std::max(dat[k], lazy[k]);lazy[k] = 0;}int update(int a, int b, int x, int k, int l, int r) {propagate(k);if (a <= l && r <= b) {lazy[k] = std::max(lazy[k], x);propagate(k);} else if (!(r <= a || b <= l)) {int lhs = update(a, b, x, 2 * k + 1, l, (l + r) / 2),rhs = update(a, b, x, 2 * k + 2, (l + r) / 2, r);dat[k] = std::max(lhs, rhs);}return dat[k];}int query(int a, int b, int k, int l, int r) {propagate(k);if (r <= a || b <= l) return 0;if (a <= l && r <= b) return dat[k];int lhs = query(a, b, 2 * k + 1, l, (l + r) / 2),rhs = query(a, b, 2 * k + 2, (l + r) / 2, r);return std::max(lhs, rhs);}int main() {int n;std::cin >> n;std::map<int, std::pair<int, int>> pos;for (int i = 0; i < n; i++) {int a;std::cin >> a;auto &e = pos[a];if (e.second) e.second = i + 1;else e = std::make_pair(i, i + 1);}for (const auto [e, p] : pos) {update(p.first, p.second, e, 0, 0, size);}for (int i = 0; i < n; i++) std::cout << query(i, i + 1, 0, 0, size) << " ";std::cout << std::endl;return 0;}