Submission #432152

#	Time	Username	Problem	Language	Result	Execution time	Memory
432152		danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	774 ms	262144 KiB

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