Submission #1230237

#TimeUsernameProblemLanguageResultExecution timeMemory
1230237vako_pSequence (APIO23_sequence)C++20
69 / 100
2009 ms76560 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; #define ll int #define pb push_back #define ff first #define sd second #define debug(x) cerr << #x << "----> " << x << endl; //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("O3") const int mxN = 5e5 + 5; ll n,a[mxN]; struct segtree{ vector<ll> mn,mx,v1,b; ll sz = 1,inf = 1e9; void init(){ while(sz < n + 5) sz *= 2; v1.assign(2 * sz, 0LL); mn.assign(2 * sz, 0LL); mx.assign(2 * sz, 0LL); for(int i = sz - 1; i < 2 * sz; i++) mx[i] = mn[i] = i - sz + 1; for(int i = sz - 2; i >= 0; i--){ mx[i] = max(mx[2 * i + 2], mx[2 * i + 1]); mn[i] = min(mn[2 * i + 2], mn[2 * i + 1]); } b.assign(n + 5, 1LL); b[0] = 0; } void f(ll x){ mx[x] += v1[x]; mn[x] += v1[x]; if(x < sz - 1){ v1[2 * x + 1] += v1[x]; v1[2 * x + 2] += v1[x]; } v1[x] = 0; } void set(ll val, ll l, ll r, ll x, ll lx, ll rx){ f(x); if(lx >= r or rx <= l) return; if(lx >= l and rx <= r){ v1[x] += val; f(x); return; } ll mid = lx + (rx - lx) / 2; set(val, l, r, 2 * x + 1, lx, mid); set(val, l, r, 2 * x + 2, mid, rx); mx[x] = max(mx[2 * x + 1], mx[2 * x + 2]); mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]); } void set(ll val, ll i){ set(val - b[i], i, n + 1, 0, 0, sz); b[i] = val; } pair<ll,ll> find(ll l, ll r, ll x, ll lx, ll rx){ f(x); if(lx >= r or rx <= l) return {1e9, -1e9}; if(lx >= l and rx <= r) return {mn[x], mx[x]}; ll mid = lx + (rx - lx) / 2; pair<ll,ll> k = find(l, r, 2 * x + 1, lx, mid),k1 = find(l, r, 2 * x + 2, mid, rx); return {min(k.ff, k1.ff), max(k.sd, k1.sd)}; } pair<ll,ll> find(ll l, ll r){ return find(l, r, 0, 0, sz); } }; int sequence(int N, std::vector<int> A) { n = N; for(int i = 1; i <= n; i++) a[i] = A[i - 1]; segtree s,s1,s2; s.init(); s1.init(); s2.init(); vector<ll> v[n + 1]; for(int i = 1; i <= n; i++){ v[a[i]].pb(i); } ll ans = 1; for(int i = 1; i <= n; i++){ ll r1 = ans - 1; vector<ll>& vv = v[i]; if(r1 < vv.size()){ for(auto it : vv){ s.set(0, it); s2.set(-1, it); } bool ok = false; pair<ll,ll> x,y; for(int l1 = 0; l1 < vv.size() and r1 < vv.size(); l1++){ int l = vv[l1],r = vv[r1]; if(!ok) x = s.find(0, l); y = s.find(r, n + 1); ok = false; if(x.sd <= y.sd){ if(s2.find(r, n + 1).ff + l1 <= x.sd) ok = true; } else{ if(x.ff <= s1.find(r, n + 1).sd - l1) ok = true; } r1++; if(ok){ ans = r1 - l1; l1--; continue; } // s1.set(0, l); // s2.set(0, l); } for(auto it : vv){ s.set(-1, it); s1.set(-1, it); // s2.set(-1, it); } } else{ for(auto it : vv){ s.set(-1, it); s1.set(-1, it); s2.set(-1, it); } } } 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...