oj.uz

Submission #674754

# Submission time Handle Problem Language Result Execution time Memory
674754 2022-12-26T07:08:32 Z onlk97 Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 589 ms 200368 KB 
#include <bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
#define dbg(A) cout<<(#A)<<" has value "<<A<<'\n';
#define dbgv(A) cout<<(#A)<<" has values ";for(auto&i:A)cout<<i<<' ';cout<<'\n';
#define dbgp(A) cout<<(#A)<<" has values ";for(auto&i:A)cout<<i.first<<", "<<i.second<<"   ";cout<<'\n';
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
using qii=pair <pii,pii>;
mt19937 mt(time(nullptr));
vector <int> seg,laz,lc,rc,marked;
void pushdown(int id,int tl,int tr){
    int tm=(tl+tr)/2;
    if (!lc[id]){
        lc[id]=lc.size();
        seg.pb(0); laz.pb(0); lc.pb(0); rc.pb(0); marked.pb(0);
    }
    if (!rc[id]){
        rc[id]=rc.size();
        seg.pb(0); laz.pb(0); lc.pb(0); rc.pb(0); marked.pb(0);
    }
    if (!marked[id]) return;
    seg[lc[id]]=laz[id]*(tm-tl+1);
    seg[rc[id]]=laz[id]*(tr-tm);
    laz[lc[id]]=laz[id];
    laz[rc[id]]=laz[id];
    marked[lc[id]]=1;
    marked[rc[id]]=1;
    marked[id]=0;
}
void update(int id,int tl,int tr,int l,int r,int val){
    if (l>r) return;
    if (l<=tl&&tr<=r){
        seg[id]=(tr-tl+1)*val;
        laz[id]=val;
        marked[id]=1;
        return;
    }
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    if (lc[id]) update(lc[id],tl,tm,l,min(r,tm),val);
    if (rc[id]) update(rc[id],tm+1,tr,max(l,tm+1),r,val);
    seg[id]=(lc[id]?seg[lc[id]]:0ll)+(rc[id]?seg[rc[id]]:0ll);
}
int query(int id,int tl,int tr,int l,int r){
    if (l>r) return 0;
    if (l<=tl&&tr<=r) return seg[id];
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    int lx=(lc[id]?query(lc[id],tl,tm,l,min(r,tm)):0ll);
    int rx=(lc[id]?query(rc[id],tm+1,tr,max(l,tm+1),r):0ll);
    return lx+rx;
}
void solve(){
    int n; cin>>n;
    int c=0;
	seg={0,0}; laz={0,0}; lc={0,0}; rc={0,0}; marked={0,0};
    for (int i=0; i<n; i++){
        int type,l,r; cin>>type>>l>>r;
        l+=c; r+=c;
        if (type==1){
            c=query(1,1,1e9,l,r);
            cout<<c<<'\n';
        } else update(1,1,1e9,l,r,1);
        //dbg(i);
        //dbgv(seg); dbgv(laz); dbgv(lc); dbgv(rc); dbgv(marked);
    }
}
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t=1;
//	cin>>t;
	while (t--) solve();
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 18 ms 4372 KB Output is correct
5 Correct 20 ms 5216 KB Output is correct
6 Correct 17 ms 5144 KB Output is correct
7 Correct 18 ms 5264 KB Output is correct
8 Correct 144 ms 37620 KB Output is correct
9 Correct 323 ms 65016 KB Output is correct
10 Correct 374 ms 71772 KB Output is correct
11 Correct 325 ms 76984 KB Output is correct
12 Correct 342 ms 79368 KB Output is correct
13 Correct 318 ms 101544 KB Output is correct
14 Correct 328 ms 101560 KB Output is correct
15 Correct 584 ms 200300 KB Output is correct
16 Correct 576 ms 200260 KB Output is correct
17 Correct 350 ms 101492 KB Output is correct
18 Correct 353 ms 101648 KB Output is correct
19 Correct 589 ms 200348 KB Output is correct
20 Correct 570 ms 200368 KB Output is correct