Submission #676540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
676540	2022-12-31T08:23:27 Z	KindaNameless	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	405 ms	200148 KB

apple

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

struct node{
    int val, lazy, tl, tr, lc, rc;

    node(int _l, int _r){
        val = 0; lazy = 0; tl = _l; tr = _r; lc = -1; rc = -1;
    }

    void oper(int add){
        if(!add)return;
        val = tr - tl + 1;
        lazy = add;
    }
};

struct segment_tree{
    vector<node> seg;

    segment_tree(){
        seg.emplace_back(node(1, 1e9));
    }

    inline int comb(int a, int b){
        return a + b;
    }

    inline void pull(int ind){
        seg[ind].val = comb(seg[seg[ind].lc].val, seg[seg[ind].rc].val);
    }

    void prop(int ind){
        if(seg[ind].tl != seg[ind].tr){
            seg[ind].oper(seg[ind].lazy);
            int m = (seg[ind].tl + seg[ind].tr) / 2;
            if(seg[ind].lc == -1){
                seg[ind].lc = (int)seg.size();
                seg.emplace_back(node(seg[ind].tl, m));
            }
            if(seg[ind].rc == -1){
                seg[ind].rc = (int)seg.size();
                seg.emplace_back(node(m+1, seg[ind].tr));
            }
            seg[seg[ind].lc].oper(seg[ind].lazy);
            seg[seg[ind].rc].oper(seg[ind].lazy);
            seg[ind].lazy = 0;
        }
    }

    void upd(int l, int r, int ind = 0){
        if(l > seg[ind].tr || r < seg[ind].tl){
            return;
        }
        if(l <= seg[ind].tl && seg[ind].tr <= r){
            seg[ind].oper(1);
            return;
        }
        prop(ind);
        upd(l, r, seg[ind].lc);
        upd(l, r, seg[ind].rc);
        pull(ind);
    }

    int query(int l, int r, int ind = 0){
        if(l > seg[ind].tr || r < seg[ind].tl){
            return 0;
        }
        if(l <= seg[ind].tl && seg[ind].tr <= r){
            seg[ind].oper(seg[ind].lazy);
            return seg[ind].val;
        }
        prop(ind);
        return comb(query(l, r, seg[ind].lc),
                    query(l, r, seg[ind].rc));
    }
};

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    segment_tree ST;

    int M; cin >> M;

    int c = 0;
    for(int i = 1; i <= M; ++i){
        int d, x, y; cin >> d >> x >> y;
        if(d == 1){
            c = ST.query(x + c, y + c);
            cout << c << "\n";
        }
        else{
            ST.upd(x + c, y + c);
        }
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	13 ms	3604 KB	Output is correct
5	Correct	16 ms	3712 KB	Output is correct
6	Correct	16 ms	3664 KB	Output is correct
7	Correct	20 ms	3696 KB	Output is correct
8	Correct	123 ms	25792 KB	Output is correct
9	Correct	247 ms	51072 KB	Output is correct
10	Correct	242 ms	50944 KB	Output is correct
11	Correct	256 ms	50816 KB	Output is correct
12	Correct	246 ms	50828 KB	Output is correct
13	Correct	256 ms	101420 KB	Output is correct
14	Correct	243 ms	101360 KB	Output is correct
15	Correct	386 ms	200148 KB	Output is correct
16	Correct	405 ms	200004 KB	Output is correct
17	Correct	289 ms	101396 KB	Output is correct
18	Correct	254 ms	101324 KB	Output is correct
19	Correct	388 ms	199980 KB	Output is correct
20	Correct	374 ms	200024 KB	Output is correct