Submission #1207660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207660		vanea	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	355 ms	205752 KiB

apple

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

const int mxN = 1e9+10;

struct Node {
    Node *left = nullptr;
    Node *right = nullptr;
    int val = 0, l, r, s = 0;

    Node (int l1, int r1) {
        l = l1; r = r1;
        val = 0; s = 0;
    }

    void extend() {
        int mid = (l + r) / 2;
        if(left == nullptr) {
            left = new Node(l, mid);
        }
        if(right == nullptr) {
            right = new Node(mid+1, r);
        }
    }

    void push() {
        int mid = (l + r) / 2;
        if(val != 0) {
            left->val = 1;
            left->s = mid-l+1;
            right->val = 1;
            right->s = r-mid;
        }
    }

    void upd(int l1, int r1) {
        if(l1 <= l && r <= r1) {
            val = 1;
            s = r-l+1;
            return ;
        }
        if(l1 > r || r1 < l) return ;
        int mid = (l + r) / 2;
        extend();
        push();
        left->upd(l1, r1);
        right->upd(l1, r1);
        s = left->s + right->s;
    }

    int qry(int l1, int r1) {
        if(l1 <= l && r <= r1) return s;
        if(l1 > r || r1 < l) return 0;
        int mid = (l+r)/2;
        extend();
        push();
        return left->qry(l1, r1) + right->qry(l1, r1);
    }

};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q, c = 0;
    cin >> q;
    Node *root = new Node(0, mxN);
    while(q--) {
        int flag;
        cin >> flag;
        int l, r;
        cin >> l >> r;
        if(flag == 1) {
            int ans = root->qry(l+c, r+c);
            c = ans;
            cout << ans << '\n';
        }
        else {
            root->upd(l+c, r+c);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100