Submission #1089497

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1089497	2024-09-16T15:29:00 Z	BLOBVISGOD	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	241 ms	106324 KB

apple

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 1e5+10;

struct node{
    int sm, lazy, l, r, lc, rc;
    int val(){
        return lazy?(r-l):sm;
    }
};

int n = 1;
node seg[81*N];

void ensure(int id){
    auto& v = seg[id];
    int mid = (v.l+v.r)/2;
    if (v.lc<0){
        seg[n] = {0,v.lazy,v.l,mid,-1,-1};
        v.lc = n++;
    }if (v.rc<0){
        seg[n] = {0,v.lazy,mid,v.r,-1,-1};
        v.rc = n++;
    }
}

void push(int id){
    ensure(id);
    auto& v = seg[id];
    if (v.lazy) seg[v.lc].lazy = v.lazy, seg[v.rc].lazy = v.lazy;
    v.sm = v.val();
    v.lazy = 0;
}

void pull(int id){
    auto& v = seg[id];
    v.sm = seg[v.lc].val() + seg[v.rc].val();
}

void ud(int i, int ql, int qr){
    auto& v = seg[i];
    if (v.l >= qr or v.r <= ql) return;
    if (v.l >= ql and v.r <= qr){
        seg[i].lazy = 1;
        return;
    }
    push(i);
    ud(v.lc,ql,qr), ud(v.rc,ql,qr);
    pull(i);
}

void update(int l, int r) {
    ud(0,l,r);
}

int gt(int i, int ql, int qr){
    auto& v = seg[i];
    if (v.l >= qr or v.r <= ql) return 0;
    if (v.l >= ql and v.r <= qr) 
        return v.val();
    push(i);
    return gt(v.lc,ql,qr) + gt(v.rc,ql,qr);
}

int get(int l, int r){
    return gt(0,l,r);
}


int main(){
    seg[0] = {0,0,0,1<<30,-1,-1};

    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int m, last = 0; cin >> m;

    while(m--){
        int t,x,y; cin >> t >> x >> y;
        x += last, y += last;
        if (t==1){
            last = get(x,y+1);
            cout << last << '\n';
        }else{
            update(x,y+1);
        }
    }

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	9 ms	2704 KB	Output is correct
5	Correct	11 ms	3220 KB	Output is correct
6	Correct	12 ms	3164 KB	Output is correct
7	Correct	11 ms	3420 KB	Output is correct
8	Correct	70 ms	23376 KB	Output is correct
9	Correct	150 ms	39636 KB	Output is correct
10	Correct	158 ms	44624 KB	Output is correct
11	Correct	165 ms	47700 KB	Output is correct
12	Correct	154 ms	49188 KB	Output is correct
13	Correct	149 ms	56956 KB	Output is correct
14	Correct	145 ms	57428 KB	Output is correct
15	Correct	206 ms	103292 KB	Output is correct
16	Correct	201 ms	104152 KB	Output is correct
17	Correct	147 ms	59220 KB	Output is correct
18	Correct	150 ms	59284 KB	Output is correct
19	Correct	216 ms	106320 KB	Output is correct
20	Correct	241 ms	106324 KB	Output is correct