結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2016-09-01 21:52:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 2,862 bytes |
コンパイル時間 | 1,413 ms |
コンパイル使用メモリ | 113,180 KB |
実行使用メモリ | 12,160 KB |
最終ジャッジ日時 | 2024-06-22 18:05:15 |
合計ジャッジ時間 | 4,896 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <array>#include <set>#include <map>#include <queue>#include <tuple>#include <unordered_set>#include <unordered_map>#include <cmath>#include <functional>#include <cassert>#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))using namespace std;template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }// TODO: generalizetemplate <typename T, typename U=T>struct starry_sky_tree {int n;vector<T> a; // elements and the cachevector<U> b; // lazied queriesfunction<T (T, T)> append; // associativefunction<U (U, U)> foo;// function<T (T, U, int)> bar;function<T (T, U)> bar;T unit;template <typename F, typename G, typename H>explicit starry_sky_tree(int a_n, T a_unit, F a_append, G a_foo, H a_bar) {n = pow(2,ceil(log2(a_n)));a.resize(2*n-1, a_unit);b.resize(2*n-1, a_unit);unit = a_unit;append = a_append;foo = a_foo;bar = a_bar;}void range_update(int l, int r, U z) {range_update(0, 0, n, l, r, z);}void range_update(int i, int il, int ir, int l, int r, U z) {if (l <= il and ir <= r) {b[i] = foo(b[i], z);a[i] = bar(a[i], z);} else if (ir <= l or r <= il) {// nop} else {range_update(2*i+1, il, (il+ir)/2, l, r, z);range_update(2*i+2, (il+ir)/2, ir, l, r, z);a[i] = bar(append(a[2*i+1], a[2*i+2]),b[i]);}}T range_concat(int l, int r) {return range_concat(0, 0, n, l, r);}T range_concat(int i, int il, int ir, int l, int r) {if (l <= il and ir <= r) {return a[i];} else if (ir <= l or r <= il) {return unit;} else {return bar(append(range_concat(2*i+1, il, (il+ir)/2, l, r),range_concat(2*i+2, (il+ir)/2, ir, l, r)),b[i]);}}};int main() {// inputint n; cin >> n;vector<int> as(n); repeat (i,n) cin >> as[i];// computemap<int,pair<int,int> > q;repeat (i,n) {if (not q.count(as[i])) q[as[i]] = { i, i };setmin(q[as[i]].first, i);setmax(q[as[i]].second, i);}auto f = [](int a, int b) { return max(a, b); };starry_sky_tree<int> t(n, 0, f, f, f);for (auto it : q) {int a = it.first;int l, r; tie(l, r) = it.second;t.range_update(l, r+1, a);}// outputrepeat (i,n) {if (i) cout << ' ';cout << t.range_concat(i, i+1);}cout << endl;return 0;}