제출 #426276

#제출 시각아이디문제언어결과실행 시간메모리
426276TLP39Progression (NOI20_progression)C++14
55 / 100
1452 ms84324 KiB
#include <stdio.h> #include <math.h> #include <utility> #include <string.h> #include <iostream> #include <vector> #include <algorithm> #include <queue> #include <map> using namespace std; typedef long long int ll; struct dev{ bool typ; ll s,c; }; struct play{ ll l,r; int len,cl,dl,cr,dr,c; }; dev rep(dev x,dev y) { if(y.typ) return y; return {x.typ,x.s+y.s,x.c+y.c}; } play mix(play x,play y) { play ans={x.l,y.r,x.len+y.len,x.cl,x.dl,y.cr,y.dr,max(x.c,y.c)}; if(x.cl==x.len) { if(x.len==1) { ans.dl=y.l-x.r; if(y.cl==1) ans.cl=2; else { if(y.dl==y.l-x.r) ans.cl=y.cl+1; else ans.cl=2; } } else { if(y.l-x.r!=x.dl) ans.cl=x.cl; else { if(y.dl==x.dl) ans.cl=x.cl+y.cl; else ans.cl=x.cl+1; } } } if(y.cr==y.len) { if(y.len==1) { ans.dr=y.l-x.r; if(x.cr==1) ans.cr=2; else { if(x.dr==y.l-x.r) ans.cr=x.cr+1; else ans.cr=2; } } else { if(y.l-x.r!=y.dr) ans.cr=y.cr; else { if(x.dr==y.dr) ans.cr=x.cr+y.cr; else ans.cr=y.cr+1; } } } if(y.l-x.r==x.dr) { if(y.l-x.r==y.dl) { ans.c=max(ans.c,x.cr+y.cl); } else { ans.c=max(ans.c,x.cr+1); } } else { if(y.l-x.r==y.dl) { ans.c=max(ans.c,1+y.cl); } else { ans.c=max(ans.c,2); } } return ans; } play mod(play x,dev y,int l,int r) { play ans=x; if(y.typ) { ans.l=y.s+(l-1)*y.c; ans.r=y.s+(r-1)*y.c; ans.cl=ans.len; ans.cr=ans.len; ans.c=ans.len; ans.dl=ans.dr=y.c; return ans; } ans.l+=(y.s+(l-1)*y.c); ans.r+=(y.s+(r-1)*y.c); ans.dl+=y.c; ans.dr+=y.c; return ans; } int n,q; ll a[300010]; play seg[1200040]; dev lz[1200040]; bool marked[1200040],bottom[1200040]; void build(int v,int st,int ed) { if(st==ed) { seg[v]={a[st],a[st],1,1,0,1,0,1}; bottom[v]=true; return; } int mid=(st+ed)>>1; build(2*v,st,mid); build(2*v+1,mid+1,ed); seg[v]=mix(seg[2*v],seg[2*v+1]); } void push_down(int v,int l,int r) { if(!marked[v] || bottom[v]) return; marked[v]=false; marked[2*v]=marked[2*v+1]=true; seg[2*v]=mod(seg[2*v],lz[v],l,r); lz[2*v]=rep(lz[2*v],lz[v]); seg[2*v+1]=mod(seg[2*v+1],lz[v],l,r); lz[2*v+1]=rep(lz[2*v+1],lz[v]); lz[v]={false,0,0}; } void upd(int v,int st,int ed,int l,int r,dev x) { if(st>ed) return; if(st==l && ed==r) { marked[v]=true; seg[v]=mod(seg[v],x,l,r); lz[v]=rep(lz[v],x); return; } push_down(v,l,r); int mid=(l+r)>>1; upd(2*v,st,min(mid,ed),l,mid,x); upd(2*v+1,max(mid+1,st),ed,mid+1,r,x); seg[v]=mix(seg[2*v],seg[2*v+1]); } play que(int v,int st,int ed,int l,int r) { if(l==st && r==ed) return seg[v]; push_down(v,l,r); int mid=(l+r)>>1; if(ed<=mid) return que(2*v,st,ed,l,mid); if(st>mid) return que(2*v+1,st,ed,mid+1,r); return mix(que(2*v,st,mid,l,mid),que(2*v+1,mid+1,ed,mid+1,r)); } int main() { scanf("%d %d",&n,&q); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=0;i<1200040;i++) { marked[i]=false; bottom[i]=false; lz[i]={false,0,0}; } build(1,1,n); int ty,l,r; ll s,c; dev temp; while(q--) { scanf("%d",&ty); if(ty==1) { scanf("%d %d %lld %lld",&l,&r,&s,&c); temp={false,s+(1-l)*c,c}; upd(1,l,r,1,n,temp); } else if(ty==2) { scanf("%d %d %lld %lld",&l,&r,&s,&c); temp={true,s+(1-l)*c,c}; upd(1,l,r,1,n,temp); } else { scanf("%d %d",&l,&r); printf("%d\n",(que(1,l,r,1,n)).c); } } }

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

Progression.cpp: In function 'int main()':
Progression.cpp:184:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
Progression.cpp:185:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
      |                           ~~~~~^~~~~~~~~~~~~~
Progression.cpp:198:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |         scanf("%d",&ty);
      |         ~~~~~^~~~~~~~~~
Progression.cpp:201:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |             scanf("%d %d %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:207:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |             scanf("%d %d %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:213:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |             scanf("%d %d",&l,&r);
      |             ~~~~~^~~~~~~~~~~~~~~
#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...