이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |