Submission #920650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
920650	2024-02-02T20:28:15 Z	Irate	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	291 ms	170064 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	1 ms	348 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	11 ms	14016 KB	Output is correct
5	Correct	13 ms	17240 KB	Output is correct
6	Correct	13 ms	17244 KB	Output is correct
7	Correct	14 ms	17416 KB	Output is correct
8	Correct	87 ms	85076 KB	Output is correct
9	Correct	187 ms	170064 KB	Output is correct
10	Correct	179 ms	169824 KB	Output is correct
11	Correct	218 ms	169824 KB	Output is correct
12	Correct	222 ms	169808 KB	Output is correct
13	Correct	171 ms	169856 KB	Output is correct
14	Correct	173 ms	169984 KB	Output is correct
15	Correct	291 ms	169928 KB	Output is correct
16	Correct	253 ms	169812 KB	Output is correct
17	Correct	171 ms	169812 KB	Output is correct
18	Correct	177 ms	169804 KB	Output is correct
19	Correct	258 ms	169808 KB	Output is correct
20	Correct	268 ms	169856 KB	Output is correct