Submission #432151

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

apple

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

#define ll long long
#define INF 1e9+7
#define lc 2*node+1
#define rc 2*node+2

#define done 0
#define add 1
#define del 2


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 = lazy = left = right = 0;
        left_child = right_child = -1;
    }
    void set(int l, int r) {
        sum = lazy = 0;
        left = l; right = r;
        left_child = right_child = -1;
    }
};

// at most Q*logN nodes will be allocated

Node segtree[70 * maxQ];


int cnt = 1;

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

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

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].set(0, MAX);


    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	87 ms	164652 KB	Output is correct
2	Correct	84 ms	164612 KB	Output is correct
3	Correct	89 ms	164728 KB	Output is correct
4	Correct	106 ms	164676 KB	Output is correct
5	Correct	126 ms	164676 KB	Output is correct
6	Correct	119 ms	164676 KB	Output is correct
7	Correct	117 ms	164608 KB	Output is correct
8	Correct	285 ms	164848 KB	Output is correct
9	Correct	507 ms	165116 KB	Output is correct
10	Correct	485 ms	164956 KB	Output is correct
11	Correct	514 ms	164980 KB	Output is correct
12	Correct	496 ms	164960 KB	Output is correct
13	Correct	440 ms	165116 KB	Output is correct
14	Correct	477 ms	165048 KB	Output is correct
15	Runtime error	769 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-