Submission #550660

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
550660	2022-04-18T19:22:15 Z	Vladth11	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	192 ms	65536 KB

apple

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 100001;
const ll VMAX = 10000001;
const ll INF = (1LL << 55);
const ll MOD = 1000007;
const ll BLOCK = 1000000;
const ll base = 1000000001;
const ll nr_of_bits = 18;

struct node {
    int l, r;
    int sum;
    int lazy;
    void init() {
        l = r = -1;
        lazy = sum = 0;
    }
} aint[NMAX * 20];

int nodes;

void propaga(int node, int st, int dr) {
    if(aint[node].lazy == 0)
        return;
    if(st != dr) {
        if(aint[node].l == -1) {
            aint[node].l = ++nodes;
            aint[nodes].init();
        }
        if(aint[node].r == -1) {
            aint[node].r = ++nodes;
            aint[nodes].init();
        }
        aint[aint[node].l].lazy = aint[aint[node].r].lazy = 1;
    }
    aint[node].lazy = 0;
    aint[node].sum = (dr - st + 1);
}

void update(int node, int st, int dr, int l, int r) {
    propaga(node, st, dr);
    if(l <= st && dr <= r) {
        aint[node].lazy = 1;
        return;
    }
    int mid = (st + dr) / 2;
    if(aint[node].l == -1) {
        aint[node].l = ++nodes;
        aint[nodes].init();
    }
    if(aint[node].r == -1) {
        aint[node].r = ++nodes;
        aint[nodes].init();
    }
    if(l <= mid) {
        update(aint[node].l, st, mid, l, r);
    }
    if(r > mid) {
        update(aint[node].r, mid + 1, dr, l, r);
    }
    propaga(aint[node].l, st, mid);
    propaga(aint[node].r, mid + 1, dr);
    aint[node].sum = aint[aint[node].l].sum + aint[aint[node].r].sum;
}

int query(int node, int st, int dr, int l, int r) {
    propaga(node, st, dr);
    if(l <= st && dr <= r) {
        return aint[node].sum;
    }
    int mid = (st + dr) / 2;
    if(aint[node].l == -1) {
        aint[node].l = ++nodes;
        aint[nodes].init();
    }
    if(aint[node].r == -1) {
        aint[node].r = ++nodes;
        aint[nodes].init();
    }
    int sol = 0;
    if(l <= mid) {
        sol += query(aint[node].l, st, mid, l, r);
    }
    if(r > mid) {
        sol += query(aint[node].r, mid + 1, dr, l, r);
    }
    return sol;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    nodes = 1;
    aint[nodes].init();
    int q;
    cin >> q;
    int ans = 0;
    while(q--){
        int a, b, c;
        cin >> a >> b >> c;
        b += ans;
        c += ans;
        if(a == 2){
            update(1, 1, VMAX, b, c);
        }else{
            ans = query(1, 1, VMAX, b, c);
            cout << ans << "\n";
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	11 ms	2904 KB	Output is correct
5	Correct	14 ms	3416 KB	Output is correct
6	Correct	19 ms	3284 KB	Output is correct
7	Correct	18 ms	3512 KB	Output is correct
8	Correct	130 ms	24368 KB	Output is correct
9	Runtime error	192 ms	65536 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-