Submission #986180

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986180	2024-05-20T03:30:59 Z	hanifchdn	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	340 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define uint unsigned int
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 2e5 + 5;

struct node {
    ll sum, lazy;
    node *l, *r;
    node() : sum(0), lazy(0), l(nullptr), r(nullptr) {}
};
 
node *root = new node();
 
void push(node *x, int tl, int tr) {
    if (x->lazy == 0) return;
    x->sum = tr - tl + 1;
    if (tl == tr) {
        x->lazy = 0;
        return;
    }
    if (x->l == nullptr) {
        x->l = new node();
        x->r = new node();
    }
    x->l->lazy = x->lazy;
    x->r->lazy = x->lazy;
    x->lazy = 0;
}

void update(node *x, int tl, int tr, int l, int r) {
    push(x, tl, tr);
    if (tr < l or r < tl) return;
    if (l <= tl and tr <= r) {
        x->lazy = 1;
        push(x, tl, tr);
        return;
    }
    if (x->l == nullptr) {
        x->l = new node();
        x->r = new node();
    }
    int tm = (tl + tr) / 2;
    update(x->l, tl, tm, l, r);
    update(x->r, tm + 1, tr, l, r);
    x->sum = x->l->sum + x->r->sum;
}
 
ll get(node *x, int tl, int tr, int l, int r) {
    if (tr < l or r < tl) return 0;
    push(x, tl, tr);
    int tm = (tl + tr) / 2;
    if (l <= tl and tr <= r) return x->sum;
    if (x->l == nullptr) {
        x->l = new node();
        x->r = new node();
    }
    return get(x->l, tl, tm, l, r) + get(x->r, tm + 1, tr, l, r);
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
        int d, x, y;
        cin >> d >> x >> y;
        if (d == 1) {
            c = get(root, 1, 1e9, x + c, y + c);
            cout << c << "\n";
        }
        else {
            update(root, 1, 1e9, x + c, y + c);
        }
    }   
}  

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	12 ms	7772 KB	Output is correct
5	Correct	15 ms	9304 KB	Output is correct
6	Correct	15 ms	9124 KB	Output is correct
7	Correct	15 ms	9308 KB	Output is correct
8	Correct	126 ms	69316 KB	Output is correct
9	Correct	260 ms	118612 KB	Output is correct
10	Correct	268 ms	132688 KB	Output is correct
11	Correct	276 ms	143696 KB	Output is correct
12	Correct	287 ms	148820 KB	Output is correct
13	Correct	262 ms	181332 KB	Output is correct
14	Correct	276 ms	183648 KB	Output is correct
15	Runtime error	340 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-