제출 #757804

#제출 시각아이디문제언어결과실행 시간메모리
757804Andrei서열 (APIO23_sequence)C++17
24 / 100
2084 ms47872 KiB
#include <bits/stdc++.h> using namespace std; int fr[500005]; vector <int> pos[500005]; /** 1 <= l <= pos[i][j] pos[i][j+x-1] + 1 <= r <= n 0000000****111 abs(cnt[-1]-cnt[1]) <= x abs(cnt[1]-cnt[-1]) <= x abs(pref[r] - pref[l]) <= x -x <= pref[r] - pref[l] <= x pref[l] - pref[r] <= x sau pref[r] - pref[l] <= x [a,b] [c,d] [a-x,b+x] trebuie sa se intersecteze cu [c,d] */ struct LazySegmentTree { int n; int aux[500005]; int minim[2000005]; int maxim[2000005]; int lazy[2000005]; void build(int i,int x,int y) { lazy[i]=0; if(x==y) minim[i]=maxim[i]=aux[x]; else { int mid=(x+y)/2; build(2*i,x,mid); build(2*i+1,mid+1,y); minim[i]=min(minim[2*i],minim[2*i+1]); maxim[i]=max(maxim[2*i],maxim[2*i+1]); } } void init(int _n) { n=_n; for(int i=0; i<=n; i++) aux[i]=i; build(1,0,n); } void propag(int i,int x,int y) { if(x!=y) { lazy[2*i]+=lazy[i]; lazy[2*i+1]+=lazy[i]; minim[2*i]+=lazy[i]; maxim[2*i]+=lazy[i]; minim[2*i+1]+=lazy[i]; maxim[2*i+1]+=lazy[i]; lazy[i]=0; } } void update(int i,int x,int y,int l,int r,int v) { propag(i,x,y); if(l<=x && y<=r) { lazy[i]+=v; minim[i]+=v; maxim[i]+=v; propag(i,x,y); } else { int mid=(x+y)/2; if(l<=mid) update(2*i,x,mid,l,r,v); if(r>mid) update(2*i+1,mid+1,y,l,r,v); minim[i]=min(minim[2*i],minim[2*i+1]); maxim[i]=max(maxim[2*i],maxim[2*i+1]); } } pair <int,int> query(int i,int x,int y,int l,int r) { propag(i,x,y); if(l<=x && y<=r) return make_pair(minim[i],maxim[i]); int mid=(x+y)/2; pair <int,int> aux=make_pair(n,-n); if(l<=mid) aux=query(2*i,x,mid,l,r); if(r>mid) { pair <int,int> temp; temp=query(2*i+1,mid+1,y,l,r); aux.first=min(aux.first,temp.first); aux.second=max(aux.second,temp.second); } return aux; } } sgt; bool ok(int n,int x) { sgt.init(n); for(int i=1; i<=n; i++) { for(auto it:pos[i]) sgt.update(1,0,n,it+1,n,-1); if(fr[i]>=x) { for(int j=0; j+x-1<fr[i]; j++) { pair <int,int> aux=sgt.query(1,0,n,0,pos[i][j]); int a=aux.first; int b=aux.second; aux=sgt.query(1,0,n,pos[i][j+x-1]+1,n); int c=aux.first; int d=aux.second; if(max(a-x,c)<=min(b+x,d)) return 1; } } for(auto it:pos[i]) sgt.update(1,0,n,it+1,n,-1); } return 0; } int sequence(int n,vector <int> a) { int mxfr=0; for(int i=0; i<n; i++) { fr[a[i]]++; mxfr=max(mxfr,fr[a[i]]); pos[a[i]].push_back(i); } int st=1,dr=mxfr,mij; while(st<=dr) { mij=(st+dr)/2; if(ok(n,mij)==1) st=mij+1; else dr=mij-1; } return st-1; } /* int n; vector <int> a; int main() { cin>>n; for(int i=0; i<n; i++) { int x; cin>>x; a.push_back(x); } cout<<sequence(n,a)<<"\n"; return 0; } */
#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...