제출 #763218

#제출 시각아이디문제언어결과실행 시간메모리
763218penguin133서열 (APIO23_sequence)C++17
100 / 100
1704 ms135228 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int n; struct node{ int s, e, m; int mx, mn, lazy; node *l, *r; node(int _s, int _e){ s = _s, e = _e, m = (s + e) >> 1; if(s != e)l = new node(s, m), r = new node(m+1, e); lazy = 0; mn = s + 1, mx = e + 1; } inline void prop(){ if(!lazy)return; mx += lazy, mn += lazy; if(s != e)l->lazy += lazy, r->lazy += lazy; lazy = 0; } inline void upd(int a, int b, int c){ if(a == s && b == e)lazy += c; else{ if(b <= m)l->upd(a, b, c); else if(a > m)r->upd(a, b, c); else l->upd(a, m, c), r->upd(m+1, b, c); l->prop(), r->prop(); mn= min(l->mn, r->mn); mx= max(l->mx, r->mx); } } inline pi qry(int a, int b){ prop(); if(a == s && b == e)return {mn, mx}; if(b <= m)return l->qry(a, b); else if(a > m)return r->qry(a, b); else{ pi lft = l->qry(a, m), rgt = r->qry(m+1 ,b); return {min(lft.fi, rgt.fi), max(lft.se, rgt.se)}; } } inline int qm(int a, int b){ prop(); if(a == s && b == e)return mx; if(b <= m)return l->qm(a, b); if(a > m)return r->qm(a, b); return max(l->qm(a, m), r->qm(m+1, b)); } inline int qmm(int a, int b){ prop(); if(a == s && b == e)return mn; if(b <= m)return l->qmm(a, b); if(a > m)return r->qmm(a, b); return min(l->qmm(a, m), r->qmm(m+1, b)); } }*lft; struct node2{ int s, e, m; int mx, mn, lazy; node2 *l, *r; node2(int _s, int _e){ s = _s, e = _e, m = (s + e) >> 1; if(s != e)l = new node2(s, m), r = new node2(m+1, e); lazy = 0, mx = (n - s), mn = (n - e); } inline void prop(){ if(!lazy)return; mx += lazy, mn += lazy; if(s != e)l->lazy += lazy, r->lazy += lazy; lazy = 0; } inline void upd(int a, int b, int c){ if(a == s && b == e)lazy += c; else{ if(b <= m)l->upd(a, b, c); else if(a > m)r->upd(a, b, c); else l->upd(a, m, c), r->upd(m+1, b, c); l->prop(), r->prop(); mn= min(l->mn, r->mn); mx= max(l->mx, r->mx); } } inline int qm(int a, int b){ prop(); if(a == s && b == e)return mx; if(b <= m)return l->qm(a, b); if(a > m)return r->qm(a, b); return max(l->qm(a, m), r->qm(m+1, b)); } inline int qmm(int a, int b){ prop(); if(a == s && b == e)return mn; if(b <= m)return l->qmm(a, b); if(a > m)return r->qmm(a, b); return min(l->qmm(a, m), r->qmm(m+1, b)); } }*rgt; vector <int> occ[500005]; int B[10][500001], lf[500005], rg[500005]; inline void upd(int f[], int l, int r, int v){ l++; r += 2; for(;l<=n;l+=(l & -l))f[l] += v; for(;r<=n;r+=(r & -r))f[r] -= v; } inline int qr(int f[], int p){ p++; int res = 0; for(;p;p-=(p & -p))res += f[p]; return res; } int sequence(int N, vector <int> A){ n = N; for(int i=0;i<N;i++)occ[A[i]].push_back(i); lft = new node(0, N - 1); rgt = new node2(0, N - 1); int ans = 1; for(int i=0;i<N;i++){ upd(lf, i, N, 1); upd(rg, 0, i, 1); } for(int i=1;i<=N;i++){ int in = 0; for(int j = 0; j < (int)occ[i].size(); j++){ int r = occ[i][j]; int tmp2 = lft->qm(r, N - 1), ref2 = qr(lf, r), tmp = rgt->qm(0, r); int ref = qr(rg, r); tmp -= ref; int tmp5 = (r == 0 ? 0 : ref2 - 1); tmp2 -= ref2; B[0][j] = tmp, B[1][j] = ref, B[2][j] = tmp2, B[3][j] = ref2, B[8][j] = tmp5; } for(auto j : occ[i]){ lft->upd(j, N - 1, -2); rgt->upd(0, j, -2); upd(lf, j, N - 1, -2); upd(rg, 0, j, -2); } for(int j = 0; j < (int)occ[i].size(); j++){ int r = occ[i][j]; int tmp4 = lft->qmm(r, N - 1), ref4 = qr(lf, r); tmp4 -= ref4; int tmp3 = rgt->qmm(0, r); int ref3 = qr(rg, r); tmp3 -= ref3; int tmp6 = (r == 0 ? 0 : ref4 + 1); B[4][j] = tmp3, B[5][j] = ref3, B[6][j] = tmp4, B[7][j] = ref4, B[9][j] = tmp6; int tmp2 = B[2][j], ref2 = B[3][j]; while(in + ans <= j){ int tmp = B[0][in]; tmp3 = B[4][in], ref3 = B[5][in]; tmp += tmp2; tmp3 += tmp4; int val = ref2 - B[8][in]; int val2 = ref4 - B[9][in]; long long mn = val + tmp, mx = val2 + tmp3; if(mn * mx > 0)in++; else break; } //cout << i << ' ' << j << ' ' << in << '\n'; ans = max(ans, j - in + 1); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...