Submission #432152

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

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

#define ll long long
#define INF 1e9+7
#define lc 2*node+1
#define rc 2*node+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	84 ms	164632 KB	Output is correct
2	Correct	87 ms	164668 KB	Output is correct
3	Correct	84 ms	164572 KB	Output is correct
4	Correct	105 ms	164700 KB	Output is correct
5	Correct	107 ms	164676 KB	Output is correct
6	Correct	108 ms	164608 KB	Output is correct
7	Correct	107 ms	164652 KB	Output is correct
8	Correct	275 ms	164836 KB	Output is correct
9	Correct	461 ms	164964 KB	Output is correct
10	Correct	503 ms	165000 KB	Output is correct
11	Correct	523 ms	165052 KB	Output is correct
12	Correct	511 ms	165064 KB	Output is correct
13	Correct	445 ms	165060 KB	Output is correct
14	Correct	449 ms	165244 KB	Output is correct
15	Runtime error	774 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-