# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1063789 | Drifter24 | Monkey and Apple-trees (IZhO12_apple) | C++17 | 362 ms | 207804 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long T;
T null=0, noVal=0;
T oper(T a, T b){return a+b;}
struct Node{
T val,lz;
int l,r;
Node *pl,*pr;
Node(int ll, int rr){
val=null;lz=noVal;
pl=pr=nullptr;
l=ll;r=rr;
}
};
typedef Node* PNode;
void update(PNode x){
if(x->r-x->l==1)return;
x->val=oper(x->pl->val, x->pr->val);
}
void extends(PNode x){
if(x->r-x->l!=1 && !x->pl){
int m=(x->r+x->l)/2;
x->pl=new Node(x->l, m);
x->pr=new Node(m, x->r);
}
}
void propagate(PNode x){
if(x->r-x->l==1)return;
if(x->lz==noVal)return;
int m=(x->r+x->l)/2;
x->pl->lz=1;
x->pl->val=m-x->l;
x->pr->lz=1;
x->pr->val=x->r-m;
x->lz=noVal;
}
struct SegTree{
PNode root;
void upd(PNode x, int l, int r, T v){
int lx=x->l,rx=x->r;
if(lx>=r || l>=rx)return;
if(lx>=l && rx<=r){
x->lz=1;
x->val=rx-lx;
return;
}
extends(x);
propagate(x);
upd(x->pl,l,r,v);
upd(x->pr,l,r,v);
update(x);
}
T get(PNode x, int l, int r){
int lx=x->l,rx=x->r;
if(lx>=r || l>=rx)return null;
if(lx>=l && rx<=r)return x->val;
extends(x);
propagate(x);
T v1=get(x->pl,l,r);
T v2=get(x->pr,l,r);
return oper(v1,v2);
}
void upd(int l, int r, T v){upd(root,l,r+1,v);}
T get(int l, int r){return get(root,l,r+1);}
void build(int l, int r){root=new Node(l, r+1);}
};
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
int q;
cin>>q;
T ans=0,op,l,r;
SegTree st;
st.build(1,1e9);
while(q--){
cin>>op>>l>>r;
l+=ans;
r+=ans;
if(op==1ll){
ans=st.get(l,r);
cout<<ans<<"\n";
}else{
st.upd(l,r,1ll);
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |