## 답안 #490096

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490096 2021-11-25T14:18:36 Z stefantaga 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
405 ms 207940 KB
```#include <bits/stdc++.h>

using namespace std;
struct Arbore{
int st,dr;
Arbore *fiust,*fiudr;
int suma,lazy;
Arbore (int l,int r)
{
st=l;
dr=r;
suma=lazy=0;
fiust=fiudr=NULL;
}
};
void propaga(Arbore *&acum,Arbore *&fiust, Arbore *&fiudr, int st,int dr)
{
if (st==dr)
{
return;
}
if (acum->lazy==0)
{
return;
}
int mij=(st+dr)/2;
if (fiust==NULL)
{
fiust = new Arbore(st,mij);
}
if (fiudr==NULL)
{
fiudr = new Arbore(mij+1,dr);
}
fiust->lazy=1;
fiust->suma=fiust->dr-fiust->st+1;
fiudr->lazy=1;
fiudr->suma=fiudr->dr-fiudr->st+1;
acum->lazy=0;
}
void update(Arbore *&acum,int st,int dr,int ua,int ub)
{
if (ub<st||dr<ua)
{
return;
}
if (acum==NULL)
{
acum = new Arbore (st,dr);
}
if (ua<=st&&dr<=ub)
{
acum->suma=dr-st+1;
acum->lazy=1;
return;
}
propaga(acum,acum->fiust,acum->fiudr,st,dr);
int mij=(st+dr)/2;
update(acum->fiust,st,mij,ua,ub);
update(acum->fiudr,mij+1,dr,ua,ub);
int stanga,dreapta;
if (acum->fiust==NULL)
{
stanga=0;
}
else
{
stanga=acum->fiust->suma;
}
if (acum->fiudr==NULL)
{
dreapta=0;
}
else
{
dreapta=acum->fiudr->suma;
}
acum->suma=stanga+dreapta;
}
int query(Arbore *&acum, int st,int dr,int ua,int ub)
{
if (ub<st||dr<ua)
{
return 0;
}
if (acum==NULL)
{
return 0;
}
if (ua<=st&&dr<=ub)
{
return acum->suma;
}
propaga(acum,acum->fiust,acum->fiudr,st,dr);
int mij=(st+dr)/2;
return query(acum->fiust,st,mij,ua,ub)+query(acum->fiudr,mij+1,dr,ua,ub);
}
int n,i;
Arbore *arb;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>n;
int lim=1e9;
arb = new Arbore (1,lim);
int sol=0;
for (i=1;i<=n;i++)
{
int tip,st,dr;
cin>>tip>>st>>dr;
st+=sol;
dr+=sol;
if (tip==1)
{
sol=query(arb,1,lim,st,dr);
cout<<sol<<'\n';
}
else
{
update(arb,1,lim,st,dr);
}
}
return 0;
}
```

#### Subtask #1 100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 12 ms 4876 KB Output is correct
5 Correct 19 ms 5964 KB Output is correct
6 Correct 16 ms 5836 KB Output is correct
7 Correct 16 ms 5964 KB Output is correct
8 Correct 124 ms 44552 KB Output is correct
9 Correct 253 ms 77228 KB Output is correct
10 Correct 264 ms 85060 KB Output is correct
11 Correct 285 ms 91020 KB Output is correct
12 Correct 275 ms 93972 KB Output is correct
13 Correct 244 ms 109216 KB Output is correct
14 Correct 299 ms 110956 KB Output is correct
15 Correct 397 ms 201772 KB Output is correct
16 Correct 405 ms 203056 KB Output is correct
17 Correct 256 ms 114880 KB Output is correct
18 Correct 303 ms 114820 KB Output is correct
19 Correct 405 ms 207940 KB Output is correct
20 Correct 393 ms 207608 KB Output is correct