제출 #749203

#제출 시각아이디문제언어결과실행 시간메모리
749203kshitij_sodani서열 (APIO23_sequence)C++17
100 / 100
1585 ms52040 KiB
#include <bits/stdc++.h> using namespace std; #define a first #define b second #define pb push_back typedef long long llo; #define endl '\n' #include "sequence.h" #include <vector> vector<int> it; int ans=0; int tree[4*500001][2]; int lazy[4*500001]; void build(int no,int l,int r){ lazy[no]=0; if(l==r){ tree[no][0]=r+1; tree[no][1]=-(r+1); } if(l<r){ int mid=(l+r)/2; build(no*2+1,l,mid); build(no*2+2,mid+1,r); tree[no][0]=max(tree[no*2+1][0],tree[no*2+2][0]); tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]); } } void push(int no,int l,int r){ tree[no][0]+=lazy[no]; tree[no][1]-=lazy[no]; if(l<r){ lazy[no*2+1]+=lazy[no]; lazy[no*2+2]+=lazy[no]; } lazy[no]=0; } void update(int no,int l,int r,int aa,int bb,int x){ push(no,l,r); if(r<aa or l>bb or aa>bb){ return ; } if(aa<=l and r<=bb){ lazy[no]=x; push(no,l,r); } else{ int mid=(l+r)/2; update(no*2+1,l,mid,aa,bb,x); update(no*2+2,mid+1,r,aa,bb,x); tree[no][0]=max(tree[no*2+1][0],tree[no*2+2][0]); tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]); } } int query(int no,int l,int r,int aa,int bb,int x){ push(no,l,r); if(r<aa or l>bb or aa>bb){ return -1e8; } if(aa<=l and r<=bb){ return tree[no][x]; //return {tree[no][0],tree[no][1]}; } int mid=(l+r)/2; return max(query(no*2+1,l,mid,aa,bb,x),query(no*2+2,mid+1,r,aa,bb,x)); /* int mid=(l+r)/2; pair<int,int> x=query(no*2+1,l,mid,aa,bb); pair<int,int> y=query(no*2+2,mid+1,r,aa,bb); tree[no][0]=max(tree[no*2+1][0],tree[no*2+2][0]); tree[no][1]=min(tree[no*2+1][1],tree[no*2+2][1]); return {max(x.a,y.a),min(x.b,y.b)};*/ } int xa; int ya; void query4(int no,int l,int r,int i){ if(r<=i){ ya=max(ya,tree[no][1]); return; } if(l>i){ xa=max(xa,tree[no][0]); return; } int mid=(l+r)/2; query4(no*2+1,l,mid,i); query4(no*2+2,mid+1,r,i); } int tree2[4*500001]; void update2(int no,int l,int r,int i,int x){ if(l==r){ tree2[no]=x; } else{ int mid=(l+r)/2; if(i<=mid){ update2(no*2+1,l,mid,i,x); } else{ update2(no*2+2,mid+1,r,i,x); } tree2[no]=max(tree2[no*2+1],tree2[no*2+2]); } } int query2(int no,int l,int r,int aa,int bb){ if(r<aa or l>bb or aa>bb){ return -1e8; } if(aa<=l and r<=bb){ return tree2[no]; } int mid=(l+r)/2; return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb)); } int query3(int no,int l,int r,int x){ if(l==r){ return l; } int mid=(l+r)/2; if(tree2[no*2+1]>=x){ return query3(no*2+1,l,mid,x); } return query3(no*2+2,mid+1,r,x); } int ind5[500001]; vector<int> pre[500001]; void solve(int n){ for(int i=0;i<n;i++){ pre[i].clear(); } for(int i=0;i<n;i++){ pre[it[i]].pb(i); } build(0,0,n); for(int i=0;i<n;i++){ if(pre[i].size()==1){ for(auto j:pre[i]){ update(0,0,n,j+1,n,-2); } } if(pre[i].size()>1){ for(auto j:pre[i]){ update(0,0,n,j+1,n,-1); } vector<pair<int,int>> zz; for(int j=0;j<pre[i].size();j++){ ind5[pre[i][j]]=j; zz.pb({-query(0,0,n,pre[i][j],pre[i][j],0),j}); } sort(zz.begin(),zz.end()); int nn=zz.size(); for(int j=0;j<4*nn;j++){ tree2[j]=-1e8; } for(auto j:zz){ int ha=-j.a; xa=-1e8; ya=-1e8; query4(0,0,n,pre[i][j.b]); int x=xa-ha; //cur=x+j.a.a+1 llo ac=-(x+j.b+1+ha);//query(0,0,n,j.b.b,j.b.b).a); //find min index with sum>=ac llo low=0; if(tree2[0]>=ac){ /* llo low=query3(0,0,n-1,ac); if(low<pre[i][j.b]){ ans=max(ans,j.b-ind5[low]+1); }*/ int low=query3(0,0,nn-1,ac); if(low<j.b){ ans=max(ans,j.b-low+1); } } int y=ha+ya;//.b; //update2(0,0,n-1,pre[i][j.b],y-j.b-ha); update2(0,0,nn-1,j.b,y-j.b-ha); } for(auto j:pre[i]){ update(0,0,n,j+1,n,-1); //update2(0,0,n-1,j,-(1e8)); } } } } int sequence(int n,vector<int> aa) { it=aa; for(int i=0;i<n;i++){ it[i]--; } ans=1; solve(n); for(int i=0;i<n;i++){ it[i]=n-1-it[i]; } solve(n); return ans; }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'void solve(int)':
sequence.cpp:154:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |    for(int j=0;j<pre[i].size();j++){
      |                ~^~~~~~~~~~~~~~
sequence.cpp:172:9: warning: unused variable 'low' [-Wunused-variable]
  172 |     llo low=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...