Submission #337220

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
337220	2020-12-19T01:12:35 Z	smax	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	672 ms	262144 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	21 ms	5996 KB	Output is correct
5	Correct	26 ms	7276 KB	Output is correct
6	Correct	26 ms	7040 KB	Output is correct
7	Correct	26 ms	7276 KB	Output is correct
8	Correct	193 ms	52460 KB	Output is correct
9	Correct	375 ms	89268 KB	Output is correct
10	Correct	401 ms	100076 KB	Output is correct
11	Correct	411 ms	108268 KB	Output is correct
12	Correct	417 ms	111980 KB	Output is correct
13	Correct	415 ms	139228 KB	Output is correct
14	Correct	413 ms	140396 KB	Output is correct
15	Correct	671 ms	254688 KB	Output is correct
16	Correct	672 ms	256784 KB	Output is correct
17	Correct	423 ms	145516 KB	Output is correct
18	Correct	428 ms	145556 KB	Output is correct
19	Correct	665 ms	262144 KB	Output is correct
20	Correct	664 ms	262144 KB	Output is correct