Submission #337220

#	Time	Username	Problem	Language	Result	Execution time	Memory
337220		smax	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	672 ms	262144 KiB

apple

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

struct Node {
    int ans;
    bool lazy;
    Node *left, *right;

    Node() : ans(0), lazy(false), left(NULL), right(NULL) {}
};

void push(Node *p, int l, int r) {
    if (p && p->lazy) {
        p->ans = r - l + 1;
        p->lazy = false;
        if (l != r) {
            if (!p->left)
                p->left = new Node();
            if (!p->right)
                p->right = new Node();
            p->left->lazy = p->right->lazy = true;
        }
    }
}

int query(Node *p, int l, int r, int i, int j) {
    if (i > r || j < l || !p)
        return 0;
    if (i <= l && r <= j)
        return p->ans;
    int m = (l + r) / 2;
    push(p->left, l, m);
    push(p->right, m+1, r);
    return query(p->left, l, m, i, j) + query(p->right, m+1, r, i, j);
}

void update(Node* &p, int l, int r, int i, int j) {
    if (i > r || j < l)
        return;
    if (!p)
        p = new Node();
    if (i <= l && r <= j) {
        p->lazy = true;
        push(p, l, r);
        return;
    }
    int m = (l + r) / 2;
    push(p->left, l, m);
    push(p->right, m+1, r);
    update(p->left, l, m, i, j);
    update(p->right, m+1, r, i, j);
    p->ans = (p->left ? p->left->ans : 0) + (p->right ? p->right->ans : 0);
}

const int MAX = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m;
    cin >> m;
    int c = 0;
    Node *st = new Node();
    for (int i=0; i<m; i++) {
        int d, x, y;
        cin >> d >> x >> y;
        if (d == 1)
            cout << (c = query(st, 1, MAX, x + c, y + c)) << "\n";
        else
            update(st, 1, MAX, x + c, y + c);
    }

    return 0;
}

• Subtask 1: 100 / 100