Submission #1093427

#TimeUsernameProblemLanguageResultExecution timeMemory
1093427alexander707070Sequence (APIO23_sequence)C++17
28 / 100
2061 ms56828 KiB
#include<bits/stdc++.h> #define MAXN 500007 using namespace std; int n,a[MAXN],ans,c[MAXN]; vector<int> poss[MAXN]; struct node{ int sum; int minpref,maxpref; int minsuff,maxsuff; inline friend node operator + (node fr,node sc){ return {fr.sum+sc.sum,min(fr.minpref,fr.sum+sc.minpref),max(fr.maxpref,fr.sum+sc.maxpref), min(sc.minsuff,sc.sum+fr.minsuff),max(sc.maxsuff,sc.sum+fr.maxsuff)}; } }curr; struct ST{ node tree[4*MAXN]; void update(int v,int l,int r,int pos,int val){ if(l==r){ tree[v].sum=val; if(val==1)tree[v].minpref=0; else tree[v].minpref=-1; if(val==-1)tree[v].maxpref=0; else tree[v].maxpref=1; if(val==1)tree[v].minsuff=0; else tree[v].minsuff=-1; if(val==-1)tree[v].maxsuff=0; else tree[v].maxsuff=1; }else{ int tt=(l+r)/2; if(pos<=tt)update(2*v,l,tt,pos,val); else update(2*v+1,tt+1,r,pos,val); tree[v]=tree[2*v]+tree[2*v+1]; } } node getinfo(int v,int l,int r,int ll,int rr){ if(ll>rr)return {0,0,0,0,0}; if(l==ll and r==rr){ return tree[v]; }else{ int tt=(l+r)/2; return getinfo(2*v,l,tt,ll,min(tt,rr)) + getinfo(2*v+1,tt+1,r,max(tt+1,ll),rr); } } }seg; bool solve(int val,int len){ for(int ii=0;ii+len-1<poss[val].size();ii++){ int ff=ii+len-1; int i=poss[val][ii]; int f=poss[val][ff]; int sum=seg.getinfo(1,1,n,i+1,f-1).sum; curr=seg.getinfo(1,1,n,f+1,n); int minpref=curr.minpref,maxpref=curr.maxpref; curr=seg.getinfo(1,1,n,1,i-1); int minsuff=curr.minsuff,maxsuff=curr.maxsuff; if((ff-ii+1)>=sum+minpref+minsuff and (ff-ii+1)>=-sum-maxpref-maxsuff)return true; } return false; } bool check(int len){ for(int i=1;i<=n;i++){ seg.update(1,1,n,i,1); } for(int i=1;i<=n;i++){ for(int f:poss[i-1])seg.update(1,1,n,f,-1); for(int f:poss[i])seg.update(1,1,n,f,0); if(solve(i,len))return true; } return false; } int sequence(int N, std::vector<int> A){ n=N; for(int i=1;i<=n;i++)poss[i].clear(); for(int i=1;i<=n;i++){ a[i]=A[i-1]; poss[a[i]].push_back(i); } int l=1,r=n+1,tt; while(l+1<r){ tt=(l+r)/2; if(check(tt)){ l=tt; }else{ r=tt; } } return l; } /*int main(){ cout<<sequence(9, {4,1,2,3,4,5,6,7,4})<<"\n"; return 0; }*/

Compilation message (stderr)

sequence.cpp: In function 'bool solve(int, int)':
sequence.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int ii=0;ii+len-1<poss[val].size();ii++){
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~
#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...