Submission #550671

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
550671	2022-04-18T19:30:09 Z	Vladth11	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	141 ms	222784 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) {
    if(aint[node].sum == dr - st + 1){
        return;
    }
    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(aint[node].sum == 0) return 0;
    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	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	8 ms	1620 KB	Output is correct
5	Correct	8 ms	1876 KB	Output is correct
6	Correct	8 ms	1748 KB	Output is correct
7	Correct	7 ms	1920 KB	Output is correct
8	Correct	44 ms	12876 KB	Output is correct
9	Correct	84 ms	22292 KB	Output is correct
10	Correct	89 ms	24396 KB	Output is correct
11	Correct	90 ms	25952 KB	Output is correct
12	Correct	96 ms	26700 KB	Output is correct
13	Runtime error	141 ms	222784 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-