제출 #1228280

#제출 시각아이디문제언어결과실행 시간메모리
1228280DzadzoSequence (APIO23_sequence)C++20
69 / 100
1945 ms80548 KiB
#include <bits/stdc++.h> #include "sequence.h" #define ll long long // #define int ll #define pb push_back #define S second #define F first #define pii pair<int,int> #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vp vector<pii> #define vvp vector<vp> #define vb vector<bool> #define vvb vector<vb> #define INF 1000000000000000 #define MOD 1000000007 #define MAXN 200000 using namespace std; // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") struct LazySegTree { struct Node { int mn, mx, add; Node(): mn(INT_MAX), mx(INT_MIN), add(0) {} }; int n; vector<Node> st; LazySegTree(int _n): n(_n) { st.resize(4*(n+1)); } void build(int p, int l, int r, const vector<int>& a) { if (l == r) { st[p].mn = st[p].mx = a[l]; return; } int m = (l + r) >> 1; build(p<<1, l, m, a); build(p<<1|1, m+1, r, a); pull(p); } void pull(int p) { st[p].mn = min(st[p<<1].mn, st[p<<1|1].mn); st[p].mx = max(st[p<<1].mx, st[p<<1|1].mx); } void apply(int p, int v) { st[p].mn += v; st[p].mx += v; st[p].add += v; } void push(int p) { if (st[p].add) { apply(p<<1, st[p].add); apply(p<<1|1, st[p].add); st[p].add = 0; } } void update(int p, int l, int r, int i, int j, int v) { if (j < l || r < i) return; if (i <= l && r <= j) { apply(p, v); return; } push(p); int m = (l + r) >> 1; update(p<<1, l, m, i, j, v); update(p<<1|1, m+1, r, i, j, v); pull(p); } int queryMin(int p, int l, int r, int i, int j) { if (j < l || r < i) return INT_MAX; if (i <= l && r <= j) return st[p].mn; push(p); int m = (l + r) >> 1; return min({queryMin(p<<1, l, m, i, j), queryMin(p<<1|1, m+1, r, i, j)}); } int queryMax(int p, int l, int r, int i, int j) { if (j < l || r < i) return INT_MIN; if (i <= l && r <= j) return st[p].mx; push(p); int m = (l + r) >> 1; return max({queryMax(p<<1, l, m, i, j), queryMax(p<<1|1, m+1, r, i, j)}); } void build(const vector<int>& a) { build(1, 1, n, a); } void Add(int l, int r, int v) { update(1, 1, n, l, r, v); } int Min(int l, int r) { return queryMin(1, 1, n, l, r); } int Max(int l, int r) { return queryMax(1, 1, n, l, r); } }; int sequence(int n, vi a) { vvi Q(n+1); reverse(a.begin(), a.end()); a.pb(0); reverse(a.begin(), a.end()); for (int i=1;i<=n;i++)Q[a[i]].pb(i); LazySegTree pmax(n),pmin(n); pmax.build(vi(n+1,0)); pmin.build(vi(n+1,0)); for (int i=1;i<=n;i++)pmin.Add(i,n,1),pmax.Add(i,n,1); int res=1; for (int i=1;i<=n;i++) { for (int x:Q[i]) { pmax.Add(x,n,-1); pmin.Add(x,n,-1); } vi prefmin(Q[i].size()),prefmax(Q[i].size()),suffmin(Q[i].size()),suffmax(Q[i].size()); for (int j=0;j<Q[i].size();j++) { int idx=Q[i][j]; if (idx>1) { prefmin[j]=pmin.Min(1,idx-1); prefmax[j]=pmax.Max(1,idx-1); } // for (int z=1;z<=n;z++)cout<<pmax.Max(z,z)<<" ";cout<<'\n'; // for (int z=1;z<=n;z++)cout<<pmin.Max(z,z)<<" ";cout<<'\n'; // cout<<'\n'; pmin.Add(1,idx,-1); pmax.Add(1,idx,1); } for (int j=0;j<Q[i].size();j++) { int idx=Q[i][j]; pmin.Add(1,idx,1); pmax.Add(1,idx,-1); } for (int j=Q[i].size()-1;j>=0;j--) { int idx=Q[i][j]; suffmin[j]=pmin.Min(idx,n); suffmax[j]=pmax.Max(idx,n); pmin.Add(idx,n,-1); pmax.Add(idx,n,1); } for (int j=Q[i].size()-1;j>=0;j--) { int idx=Q[i][j]; pmin.Add(idx,n,1); pmax.Add(idx,n,-1); } for (int x:Q[i])pmin.Add(x,n,-1),pmax.Add(x,n,-1); int L=0; for (int R=0;R<Q[i].size();R++) { // cout<<prefmin[R]<<" "<<prefmax[R]<<'\n'; // cout<<suffmin[R]<<" "<<suffmax[R]<<'\n'; while (L < R && ( suffmax[R]-prefmin[L] < - ( R - L + 1 ) || suffmin[R]-prefmax[L] > ( R - L + 1 ) ) )L++; // cout<<L<<" "<<R<<'\n'; // cout<<'\n'; res=max(res,R-L+1); } } return res; } // int main() { // cout<<sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2}); // } /* */
#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...