Submission #432156

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
432156	2021-06-17T22:24:11 Z	danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	547 ms	262148 KB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define INF 1e9+7

using namespace std;


const int MAX = 1e9 + 1;
const int maxQ = 1e5 + 1;
int m;

struct Node {
    int sum, lazy, left, right;
    int left_child, right_child;
    Node() : sum(0), lazy(0), left_child(-1), right_child(-1) {}
};

// at most Q*logN nodes will be allocated

Node segtree[64 * maxQ];


int cnt = 1;

void allocateLeft(int node, int l, int mid) {
    segtree[node].left_child = cnt++;
    segtree[cnt - 1].left = l;
    segtree[cnt - 1].right = mid;
}

void allocateRight(int node, int mid, int r) {
    segtree[node].right_child = cnt++;
    segtree[cnt - 1].left = mid + 1;
    segtree[cnt - 1].right = r;
}

void propagate(int node) {
    if (segtree[node].lazy) {
        segtree[node].sum = segtree[node].right - segtree[node].left + 1;

        if (segtree[node].left != segtree[node].right) {
            int mid = (segtree[node].left + segtree[node].right) / 2;
            if (segtree[node].left_child == -1) allocateLeft(node, segtree[node].left, mid);
            if (segtree[node].right_child == -1) allocateRight(node, mid, segtree[node].right);
            segtree[segtree[node].left_child].lazy = segtree[segtree[node].right_child].lazy = 1;
        }

        segtree[node].lazy = 0;
    }
}

void update(int node, int x, int y) {
    if (x <= segtree[node].left && segtree[node].right <= y) {
        segtree[node].lazy = 1;
    }
    else {
        propagate(node);
        int mid = (segtree[node].left + segtree[node].right) / 2;

        if (segtree[node].left_child == -1) allocateLeft(node, segtree[node].left, mid);
        if (segtree[node].right_child == -1) allocateRight(node, mid, segtree[node].right);

        if (x <= mid) update(segtree[node].left_child, x, y);
        if (y >= mid + 1) update(segtree[node].right_child, x, y);

        propagate(segtree[node].left_child); propagate(segtree[node].right_child);
        segtree[node].sum = segtree[segtree[node].left_child].sum + segtree[segtree[node].right_child].sum;
    }
}

int query(int node, int x, int y) {
    propagate(node);
    if (x <= segtree[node].left && segtree[node].right <= y) return segtree[node].sum;
    else {
        int mid = (segtree[node].left + segtree[node].right) / 2;

        if (segtree[node].left_child == -1) allocateLeft(node, segtree[node].left, mid);
        if (segtree[node].right_child == -1) allocateRight(node, mid, segtree[node].right);

        int ans = 0;
        if (x <= mid) ans += query(segtree[node].left_child, x, y);
        if (y >= mid + 1) ans += query(segtree[node].right_child, x, y);

        return ans;
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // freopen("input.in", "r", stdin);
    // freopen("input.out", "w", stdout);

    cin >> m;

    segtree[0].left = 0; segtree[0].right = 1e9;


    int t, l, r;
    int c = 0;

    while (m --) {
        cin >> t >> l >> r;
        l --; r --;
        l += c; r += c;

        if (t == 1) {
            c = query(0, l, r);
            cout << c << endl;
        }
        else { // t == 2
            update(0, l, r);
        }
    }

    return 0;

}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	150472 KB	Output is correct
2	Correct	70 ms	150488 KB	Output is correct
3	Correct	69 ms	150480 KB	Output is correct
4	Correct	90 ms	150516 KB	Output is correct
5	Correct	101 ms	150596 KB	Output is correct
6	Correct	95 ms	150568 KB	Output is correct
7	Correct	105 ms	150688 KB	Output is correct
8	Correct	243 ms	150776 KB	Output is correct
9	Correct	451 ms	150916 KB	Output is correct
10	Correct	450 ms	150980 KB	Output is correct
11	Correct	452 ms	150952 KB	Output is correct
12	Correct	464 ms	151012 KB	Output is correct
13	Correct	408 ms	151132 KB	Output is correct
14	Correct	428 ms	151036 KB	Output is correct
15	Runtime error	547 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-