Submission #894547

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894547	2023-12-28T12:23:27 Z	Andrey	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	91 ms	34280 KB

apple

#include <bits/stdc++.h>
using namespace std;

int p = 1;
vector<pair<int,int>> seg(1,{-1,-1});
vector<int> br(1);

void upd(int l, int r, int ql, int qr, int x) {
    if(l == ql && r == qr) {
        br[x] = r-l+1;
        return;
    }
    int m = (l+r)/2;
    if(qr <= m) {
        if(seg[x].first == -1) {
            seg[x] = {p,seg[x].second};
            p++;
            seg.push_back({-1,-1});
            br.push_back(0);
        }
        upd(l,m,ql,qr,seg[x].first);
    }
    else if(ql > m) {
        if(seg[x].second == -1) {
            seg[x] = {seg[x].first,p};
            p++;
            seg.push_back({-1,-1});
            br.push_back(0);
        }
        upd(m+1,r,ql,qr,seg[x].second);
    }
    else {
        if(seg[x].first == -1) {
            seg[x] = {p,seg[x].second};
            p++;
            seg.push_back({-1,-1});
            br.push_back(0);
        }
        if(seg[x].second == -1) {
            seg[x] = {seg[x].first,p};
            p++;
            seg.push_back({-1,-1});
            br.push_back(0);
        }
        upd(l,m,ql,m,seg[x].first);
        upd(m+1,r,m+1,qr,seg[x].second);
    }
    if(br[x] != r-l+1) {
        br[x] = 0;
        if(seg[x].first != -1) {
            br[x]+=br[seg[x].first];
        }
        if(seg[x].second != -1) {
            br[x]+=br[seg[x].second];
        }
    }
}

int calc(int l, int r, int ql, int qr, int x) {
    if(ql == l && qr == r) {
        return br[x];
    }
    if(br[x] == r-l+1) {
        return qr-ql+1;
    }
    int m = (l+r)/2;
    if(qr <= m) {
        if(seg[x].first != -1) {
            return calc(l,m,ql,qr,seg[x].first);
        }
    }
    else if(ql > m) {
        if(seg[x].second != -1) {
            return calc(m+1,r,ql,qr,seg[x].second);
        }
    }
    else {
        int ans = 0;
        if(seg[x].first != -1) {
            ans+=calc(l,m,ql,m,seg[x].first);
        }
        if(seg[x].second != -1) {
            ans+=calc(m+1,r,m+1,qr,seg[x].second);
        }
        return ans;
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q,l,r,p,c = 0;
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> p >> l >> r;
        l+=c;
        r+=c;
        if(p == 1) {
            c = calc(1,1e9,l,r,0);
            cout << c << "\n";
        }
        else {
            upd(1,1e9,l,r,0);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	5 ms	1152 KB	Output is correct
5	Correct	6 ms	1372 KB	Output is correct
6	Correct	6 ms	1492 KB	Output is correct
7	Correct	6 ms	1372 KB	Output is correct
8	Correct	37 ms	8264 KB	Output is correct
9	Correct	63 ms	16180 KB	Output is correct
10	Correct	65 ms	18132 KB	Output is correct
11	Correct	65 ms	17208 KB	Output is correct
12	Correct	73 ms	18032 KB	Output is correct
13	Correct	74 ms	18060 KB	Output is correct
14	Correct	65 ms	18224 KB	Output is correct
15	Correct	82 ms	32812 KB	Output is correct
16	Correct	91 ms	33836 KB	Output is correct
17	Correct	64 ms	18656 KB	Output is correct
18	Correct	64 ms	18484 KB	Output is correct
19	Correct	82 ms	33580 KB	Output is correct
20	Correct	83 ms	34280 KB	Output is correct