結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2020-09-25 23:55:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 238 ms / 2,000 ms |
コード長 | 3,846 bytes |
コンパイル時間 | 2,131 ms |
コンパイル使用メモリ | 208,328 KB |
最終ジャッジ日時 | 2025-01-14 21:45:37 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<ll, ll> p_ll;template<class T>void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }#define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)#define all(vec) vec.begin(), vec.end()#define rep(i,N) repr(i,0,N)#define per(i,N) for (int i=(int)N-1; i>=0; i--)const ll MOD = pow(10,9)+7;const ll LLINF = pow(2,61)-1;const int INF = pow(2,30)-1;vector<ll> fac;void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }// ----------------------------------------------------------------------// ----------------------------------------------------------------------struct LazySegTree {ll size;ll val_e = 0, ope_e = 1;vector<ll> val, ope;LazySegTree(ll N) {size = 1; while(size<N) size<<=1;val.resize(2*size,val_e); ope.resize(2*size,ope_e);for (ll i=size-1; i>=1; i--) val[i] = f_back(i*2, i*2+1);}ll operator[](ll x) { return query(x,x+1); }void propagation(ll x, ll y) {bool px = false, py = false;vector<ll> order;for (x+=size, y+=size; x||y; x>>=1, y>>=1) {px |= x&1; py |= y&1;if (px) order.push_back(x);if (py&&!(px&&x==y)) order.push_back(y);}for (auto itr=rbegin(order); itr!=rend(order); ++itr) {if (*itr>=size) break;ope[*itr*2] = g(ope[*itr*2] , ope[*itr]);ope[*itr*2+1] = g(ope[*itr*2+1], ope[*itr]);ope[*itr] = ope_e;}}void update_operator(ll x, ll y, ll v) {for (x+=size, y+=size; x<y; x>>=1, y>>=1) {if (x&1) { ope[x] = g(ope[x],v); x++; }if (y&1) { y--; ope[y] = g(ope[y],v); }}}void back_propagation(ll x, ll y) {for (x+=size, y+=size-1; x||y; x>>=1, y>>=1) {if (x<size) val[x] = f_back(x*2, x*2+1);if (y<size) val[y] = f_back(y*2, y*2+1);}}void set_operator(ll x, ll y, ll v) {propagation(x,y);update_operator(x,y,v);back_propagation(x,y);}void set_value(ll x, ll v) {propagation(x,x+1);val[x+size] = v;ope[x+size] = ope_e;back_propagation(x,x+1);}ll query(ll x, ll y) {propagation(x,y);ll L = 0, R = 0;for (x+=size, y+=size; x<y; x>>=1, y>>=1) {if (x&1) { L = f(L,h(val[x],ope[x])); x++; }if (y&1) { y--; R = f(h(val[y],ope[y]),R); }}return f(L,R);}void operate(ll i) { val[i] = f(val[i*2], val[i*2+1]); }ll f(ll x, ll y) { return max(x,y); }ll f_back(ll x, ll y) { return f(h(val[x],ope[x]),h(val[y],ope[y])); } // 要素同士の演算ll g(ll x, ll y) { return max(x,y); } // 作用素同士の演算ll h(ll x, ll y) { return max(x,y); } // 要素に作用素を書けるvoid output() {rep(i,size*2) cout << val[i] << "*" << ope[i] << " "; cout << endl;}};// ----------------------------------------------------------------------// ----------------------------------------------------------------------int main() {ll n; cin >> n;ll a[n]; rep(i,n) cin >> a[i];map<ll, ll> lm, rm;rep(i,n) rm[a[i]] = i;per(i,n) lm[a[i]] = i;// for (auto x: rm) cout << x.first << ":" << lm[x.first] << "-" << x.second << endl;LazySegTree lst(n); rep(i,n) lst.set_value(i,a[i]);for (auto x: rm) {if (lm[x.first]==x.second) continue;lst.set_operator(lm[x.first],x.second+1,x.first);}rep(i,n) cout << lst[i] << " "; cout << endl;// cout << result << endl;return 0;}