結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2019-09-04 11:16:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 188 ms / 2,000 ms |
コード長 | 3,138 bytes |
コンパイル時間 | 2,450 ms |
コンパイル使用メモリ | 186,396 KB |
実行使用メモリ | 16,640 KB |
最終ジャッジ日時 | 2024-12-26 04:41:39 |
合計ジャッジ時間 | 6,888 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <class T>inline bool chmax(T &a, T b){if (a < b){a = b;return 1;}return 0;}template <class T>inline bool chmin(T &a, T b){if (a > b){a = b;return 1;}return 0;}typedef long long int ll;#define EPS (1e-7)#define INF (INT_MAX)#define LLINF (1LL << 60)#define PI (acos(-1))#define MOD (1000000007)#define ALL(v) (v).begin(), (v).end()#define RALL(v) (v).rbegin(), (v).rend()const int dx[4] = {1, 0, -1, 0};const int dy[4] = {0, 1, 0, -1};//-------------------------------------struct SegTree{private:int n;vector<int> node, lazy;vector<bool> lazyFlag;public:SegTree(vector<int> &v){int sz = v.size();n = 1;while (n < sz){n *= 2;}node.resize(2 * n - 1);lazy.resize(2 * n - 1, -INF);lazyFlag.resize(2 * n - 1, false);for (int i = 0; i < sz; i++){node[i + n - 1] = v[i];}for (int i = n - 2; i >= 0; i--){node[i] = max(node[2 * i + 1], node[2 * i + 2]);}}void eval(int i, int l, int r){if (lazyFlag[i]){node[i] = lazy[i];if (r - l > 1){lazy[2 * i + 1] = lazy[2 * i + 2] = lazy[i];lazyFlag[2 * i + 1] = lazyFlag[2 * i + 2] = true;}lazyFlag[i] = false;}}void update(int a, int b, int val, int i = 0, int l = 0, int r = -1){if (r < 0){r = n;}eval(i, l, r);if (b <= l || r <= a){return;}if (a <= l && r <= b){lazy[i] = val;lazyFlag[i] = true;eval(i, l, r);}else{update(a, b, val, 2 * i + 1, l, (l + r) / 2);update(a, b, val, 2 * i + 2, (l + r) / 2, r);node[i] = max(node[2 * i + 1], node[2 * i + 2]);}}int getmax(int a, int b, int i = 0, int l = 0, int r = -1){if (r < 0){r = n;}eval(i, l, r);if (b <= l || r <= a){return -INF;}if (a <= l && r <= b){return node[i];}int mid = (l + r) / 2;int vl = getmax(a, b, 2 * i + 1, l, mid);int vr = getmax(a, b, 2 * i + 2, mid, r);return max(vl, vr);}};int main(){cin.tie(0);ios::sync_with_stdio(false);int n;cin >> n;map<int, vector<int>> mp;for (int i = 0; i < n; i++){int a;cin >> a;mp[a].push_back(i);}vector<int> v(n);SegTree seg(v);for (auto itr : mp){int val = itr.first;int l = itr.second.front();int r = itr.second.back();seg.update(l, r + 1, val);}for (int i = 0; i < n; i++){cout << seg.getmax(i, i + 1) << ' ';}cout << endl;}