| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 594492 | alexdumitru | 원숭이와 사과 나무 (IZhO12_apple) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
//ifstream fin("f.in");
//ofstream fout("f.out");
const int QMAX=10;
struct Node{
int sum,lazy,tl,tr,l,r;
Node(): sum(0),lazy(0),l(-1),r(-1) {}
} aint[QMAX*30*3];
int tip,q,x,y,c=0;
int cnt=1;
void create(int nod)
{
int mij=(aint[nod].tl+aint[nod].tr)/2;
if(aint[nod].l==-1)
{
aint[nod].l=++cnt;
aint[cnt].tl=aint[nod].tl;
aint[cnt].tr=mij;
}
if(aint[nod].r==-1)
{
aint[nod].r=++cnt;
aint[cnt].tl=mij+1;
aint[cnt].tr=aint[nod].tr;
}
}
void propag(int nod)
{
if(aint[nod].lazy)
{
aint[nod].lazy=0;
create(nod);
aint[aint[nod].l].lazy=aint[aint[nod].r].lazy=1;
aint[nod].sum=aint[nod].tr-aint[nod].tl+1;
}
}
void update(int nod, int x, int y)
{
propag(nod);
if(x==aint[nod].tl&&y==aint[nod].tr)
{
aint[nod].lazy=1;
propag(nod);
return;
}
int mij=(aint[nod].tl+aint[nod].tr)/2;
create(nod);
if(x>mij)
update(aint[nod].r,x,y);
else if(y<=mij)
update(aint[nod].l,x,y);
else {
update(aint[nod].l,x,mij);
update(aint[nod].r,mij+1,y);
}
propag(aint[nod].l);
propag(aint[nod].r);
aint[nod].sum=aint[aint[nod].l].sum+aint[aint[nod].r].sum;
}
int query(int nod, int x, int y)
{
propag(nod);
if(aint[nod].tl==x&&aint[nod].tr==y)
return aint[nod].sum;
int mij=(aint[nod].tl+aint[nod].tr)/2;
create(nod);
if(x>mij)
return query(aint[nod].r,x,y);
if(y<=mij)
return query(aint[nod].l,x,y);
return query(aint[nod].l,x,mij)+query(aint[nod].r,mij+1,y);
}
signed main()
{
aint[1].tl=1;
aint[1].tr=1e9;
cin>>q;
while(q--)
{
cin>>tip>>x>>y;
if(tip==1)
{
c=query(1,x+c,y+c);
fout<<c<<'\n';
}
else update(1,x+c,y+c);
}
return 0;
}