Submission #550674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
550674	2022-04-18T19:32:18 Z	Vladth11	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	222 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 * 30];

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 == dr - st + 1) return min(dr, r) - max(l, st) + 1;
  	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	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	4 ms	340 KB	Output is correct
5	Correct	4 ms	364 KB	Output is correct
6	Correct	5 ms	340 KB	Output is correct
7	Correct	4 ms	352 KB	Output is correct
8	Correct	16 ms	524 KB	Output is correct
9	Correct	33 ms	596 KB	Output is correct
10	Correct	30 ms	660 KB	Output is correct
11	Correct	31 ms	604 KB	Output is correct
12	Correct	34 ms	656 KB	Output is correct
13	Runtime error	222 ms	262144 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-