Submission #550664

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
550664	2022-04-18T19:24:01 Z	Vladth11	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	215 ms	262144 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 * 90];

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	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	13 ms	3044 KB	Output is correct
5	Correct	13 ms	3416 KB	Output is correct
6	Correct	13 ms	3412 KB	Output is correct
7	Correct	13 ms	3412 KB	Output is correct
8	Correct	94 ms	24232 KB	Output is correct
9	Correct	204 ms	41296 KB	Output is correct
10	Correct	205 ms	45664 KB	Output is correct
11	Correct	215 ms	49276 KB	Output is correct
12	Correct	210 ms	50836 KB	Output is correct
13	Runtime error	197 ms	262144 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-