Submission #920649

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
920649	2024-02-02T20:26:45 Z	vjudge1	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	306 ms	172296 KB

apple

#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{
    vector<int>sTree, L, R;
    int nxt = 2;
    SegmentTree(int n){
        sTree.resize(144 * n);
        L.resize(144 * n);
        R.resize(144 * n);
    }
    void Propagate(int node, int l, int r){
        if(sTree[node] != r - l + 1)return;
        if(l != r){
            if(L[node] == 0)L[node] = nxt++;
            if(R[node] == 0)R[node] = nxt++;
            int mid = (l + r) >> 1;
            sTree[L[node]] = mid - l + 1;
            sTree[R[node]] = r - mid;
        }
    }
    void R_Update(int node, int l, int r, int ql, int qr){
        Propagate(node, l, r);
        if(ql <= l && r <= qr){
            sTree[node] = r - l + 1;
            Propagate(node, l, r);
            return;
        }
        if(ql > r || l > qr)return;
        int mid = (l + r) >> 1;
        if(L[node] == 0)L[node] = nxt++;
        if(R[node] == 0)R[node] = nxt++;
        R_Update(L[node], l, mid, ql, qr);
        R_Update(R[node], mid + 1, r, ql, qr);
        sTree[node] = sTree[L[node]] + sTree[R[node]];
    }
    int Query(int node, int l, int r, int ql, int qr){
        Propagate(node, l, r);
        if(ql <= l && r <= qr){
            return sTree[node];
        }
        if(ql > r || l > qr)return 0;
        int mid = (l + r) >> 1;
        if(L[node] == 0)L[node] = nxt++;
        if(R[node] == 0)R[node] = nxt++;
        int lc = Query(L[node], l, mid, ql, qr);
        int rc = Query(R[node], mid + 1, r, ql, qr);
        return lc + rc;
    }
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q, c = 0;
    cin >> q;
    SegmentTree tree(q);
    int n = 1e9;
    while(q--){
        int type, l, r;
        cin >> type >> l >> r;
        l += c;
        r += c;
        if(type == 1){
            c = tree.Query(1, 1, n, l, r);
            cout << c << '\n';
        }
        else{
            tree.R_Update(1, 1, n, l, r);
        }
    }
}

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	1 ms	604 KB	Output is correct
4	Correct	11 ms	14132 KB	Output is correct
5	Correct	15 ms	17364 KB	Output is correct
6	Correct	13 ms	17496 KB	Output is correct
7	Correct	13 ms	17500 KB	Output is correct
8	Correct	96 ms	85960 KB	Output is correct
9	Correct	212 ms	171420 KB	Output is correct
10	Correct	216 ms	171632 KB	Output is correct
11	Correct	205 ms	171596 KB	Output is correct
12	Correct	204 ms	171600 KB	Output is correct
13	Correct	171 ms	171972 KB	Output is correct
14	Correct	174 ms	171976 KB	Output is correct
15	Correct	265 ms	172164 KB	Output is correct
16	Correct	306 ms	172088 KB	Output is correct
17	Correct	173 ms	171860 KB	Output is correct
18	Correct	176 ms	171856 KB	Output is correct
19	Correct	263 ms	172296 KB	Output is correct
20	Correct	271 ms	172116 KB	Output is correct