Submission #951374

#	Time	Username	Problem	Language	Result	Execution time	Memory
951374		sheldon	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	170 ms	128340 KiB

apple

#include <bits/stdc++.h>

using namespace std;


struct Node {
    int left = -1, right = -1, ans = 0, lazy = 0;
    int sz;


    void push (Node &l, Node &r) {
        if (lazy) {
            l.ans = l.sz;
            r.ans = r.sz;
            l.lazy = 1;
            r.lazy = 1;
            lazy = 0;
        }
    }

    void get (Node &l, Node &r) {
        ans = l.ans + r.ans;
    }
};
const int nax = 100000;
Node tree[nax * 64];
int idx = 2;

void create (int node, int l, int r) {
    if (tree[node].left == -1) {
        tree[node].left = idx;
        tree[idx].sz  = (l + r) / 2 - l + 1;
        ++idx;
    }
    // maybe l > r ???
    if (tree[node].right == -1) {
        tree[node].right = idx;
        tree[idx].sz = r - ((l + r) / 2 + 1) + 1; 
        ++idx;
    }
}


void update (int node, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) {
        return;
    }


    if (ql <= l && r <= qr) {
        tree[node].ans = r - l + 1;
        tree[node].lazy = 1;
        return;
    }

    int mid = (l + r) / 2;
    create (node, l, r);
    tree[node].push (tree[tree[node].left], tree[tree[node].right]);
    update (tree[node].left, l, mid, ql, qr);
    update (tree[node].right, mid + 1, r, ql, qr);
    tree[node].get (tree[tree[node].left], tree[tree[node].right]);
}

int query (int node, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) {
        return 0;
    }

    if (ql <= l && r <= qr) {
        return tree[node].ans;
    }

    int mid = (l + r) / 2;
    create (node, l, r);
    tree[node].push (tree[tree[node].left], tree[tree[node].right]);
    return query (tree[node].left, l, mid, ql, qr) + query (tree[node].right, mid + 1, r, ql, qr);


}

void solve() {
    int q;
    cin >> q;
    int c = 0;

    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        
        if (type == 1) {
            c = query (1, 1, 1e9 + 5, l + c, r + c);
            cout << c << '\n';
        } else {
            update (1, 1, 1e9 + 5, l + c, r + c);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

• Subtask 1: 100 / 100