제출 #749389

#제출 시각아이디문제언어결과실행 시간메모리
749389boyliguanhan서열 (APIO23_sequence)C++17
100 / 100
1157 ms89076 KiB
#include <bits/stdc++.h> #include "sequence.h" using namespace std; struct qj{ int l,r; friend qj operator+(qj a,qj b){ a.l+=b.l;a.r+=b.r; return a; } }; struct node{ int l,r,sl,is; qj it,iq,h,q,t; }p[2000005]; vector<int>wz[500005]; int res,n; void upset(int x){ p[x].t.l=p[x<<1].t.l+p[x<<1|1].t.l; p[x].t.r=p[x<<1].t.r+p[x<<1|1].t.r; p[x].q.l=min(p[x<<1].q.l,p[x<<1|1].q.l+p[x<<1].t.l); p[x].q.r=max(p[x<<1].q.r,p[x<<1|1].q.r+p[x<<1].t.r); p[x].h.l=min(p[x<<1|1].h.l,p[x<<1].h.l+p[x<<1|1].t.l); p[x].h.r=max(p[x<<1|1].h.r,p[x<<1].h.r+p[x<<1|1].t.r); p[x].sl=p[x<<1].sl+p[x<<1|1].sl; } void reset(int x,int l,int r){ p[x].l=l,p[x].r=r; if(l==r){ p[x].h.l=p[x].h.r=p[x].q.l=p[x].q.r=p[x].t.l=p[x].t.r=1; return; } int mid=l+r>>1; reset(x<<1,l,mid); reset(x<<1|1,mid+1,r); upset(x); } void sets(int x,int d,int sum){ if(p[x].l==d&&p[x].r==d){ if(sum){ p[x].h.l=p[x].h.r=p[x].q.l=p[x].q.r=p[x].t.l=p[x].t.r=sum; p[x].sl=0; }else{ p[x].h.l=p[x].q.l=p[x].t.l=-1; p[x].h.r=p[x].q.r=p[x].t.r=1; p[x].sl=1; } return; } int mid=p[x].l+p[x].r>>1; if(d<=mid)sets(x<<1,d,sum); else sets(x<<1|1,d,sum); upset(x); } void gx(int x,int sum){ for(int i=0;i<wz[x].size();i++)sets(1,wz[x][i],sum); } qj gets1(int x,int d){ if(d==0)return (qj){0,0}; if(p[x].l==p[x].r){ p[x].it=p[x].t; return p[x].t; } int mid=p[x].l+p[x].r>>1; qj res=(qj){0,0}; if(d<=mid){ qj nww=gets1(x<<1,d); p[x].it=p[x<<1].it; return nww; }else{ qj rr=gets1(x<<1|1,d); res.l=min(rr.l,p[x<<1|1].it.l+p[x<<1].h.l); res.r=max(rr.r,p[x<<1|1].it.r+p[x<<1].h.r); p[x].it=p[x<<1].t+p[x<<1|1].it; } return res; } void init(int x,int d){ if(p[x].l==p[x].r){ p[x].it=p[x].t,p[x].iq=p[x].q,p[x].is=p[x].sl; return; } if(p[x<<1].r<d){ init(x<<1|1,d); p[x].it=p[x<<1|1].it,p[x].iq=p[x<<1|1].iq,p[x].is=p[x<<1|1].is; return; } init(x<<1,d); p[x].it=p[x<<1].it+p[x<<1|1].t; p[x].iq.l=min(p[x<<1].iq.l,p[x<<1|1].q.l+p[x<<1].it.l); p[x].iq.r=max(p[x<<1].iq.r,p[x<<1|1].q.r+p[x<<1].it.r); p[x].is=p[x<<1].is+p[x<<1|1].sl; } int gets(int x,int d,qj sum,int ans,int xy){ if(p[x].l==p[x].r)return ans+p[x].sl; int mid=p[x].l+p[x].r>>1; if(d>mid)return gets(x<<1|1,d,sum,ans,1); if(xy){ qj rt=p[x<<1].it+p[x<<1|1].q+sum; if(rt.l<=0&&rt.r>=0)return gets(x<<1|1,d,sum+p[x<<1].it,ans+p[x<<1].is,0); else return gets(x<<1,d,sum,ans,1); }else{ qj rt=p[x<<1].t+p[x<<1|1].q+sum; if(rt.l<=0&&rt.r>=0)return gets(x<<1|1,d,sum+p[x<<1].t,ans+p[x<<1].sl,0); else return gets(x<<1,d,sum,ans,0); } } int sol(int x){ qj fw=gets1(1,x-1); fw.l=min(0,fw.l),fw.r=max(fw.r,0); init(1,x); return gets(1,x,fw,0,1); } int solve(int x){ int ans=0; for(int i=0;i<wz[x].size();i++){ ans=max(ans,sol(wz[x][i])); } return ans; } int sequence(int N,vector<int>w){ n=N; reset(1,1,n); for(int i=0;i<n;i++){ wz[w[i]].push_back(i+1); } for(int i=1;i<=n;i++){ gx(i-1,-1); gx(i,0); gx(i+1,1); res=max(res,solve(i)); } return res; }

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

sequence.cpp: In function 'void reset(int, int, int)':
sequence.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int mid=l+r>>1;
      |          ~^~
sequence.cpp: In function 'void sets(int, int, int)':
sequence.cpp:49:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int mid=p[x].l+p[x].r>>1;
      |          ~~~~~~^~~~~~~
sequence.cpp: In function 'void gx(int, int)':
sequence.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=0;i<wz[x].size();i++)sets(1,wz[x][i],sum);
      |              ~^~~~~~~~~~~~~
sequence.cpp: In function 'qj gets1(int, int)':
sequence.cpp:63:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |  int mid=p[x].l+p[x].r>>1;
      |          ~~~~~~^~~~~~~
sequence.cpp: In function 'int gets(int, int, qj, int, int)':
sequence.cpp:95:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |  int mid=p[x].l+p[x].r>>1;
      |          ~~~~~~^~~~~~~
sequence.cpp: In function 'int solve(int)':
sequence.cpp:115:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i=0;i<wz[x].size();i++){
      |              ~^~~~~~~~~~~~~
#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...