Submission #919874

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919874	2024-02-01T18:32:55 Z	Macker	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	464 ms	139852 KB

apple

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()

struct node{
    node* l = NULL, * r = NULL;
    int val = 0;
    int lz = 0;
};
typedef node* pnode;

void push(pnode& n){
    if(!n->l) n->l = new node();
    if(!n->r) n->r = new node();
}

void prop(pnode& n, int d){
    if(!n->lz) return;
    push(n);
    n->l->val = d / 2;
    n->r->val = d / 2;
    n->l->lz = 1;
    n->r->lz = 1;
    n->lz = 0;
}

void upd(int l, int r, pnode& n, int s = 0, int e = 2147483647){
    if(l >= e || r <= s) return;
    if(l <= s && e <= r){
        n->val = e - s;
        n->lz = 1;
        return;
    }
    push(n);
    prop(n, e - s);

    upd(l, r, n->l, s, (s + e) / 2);
    upd(l, r, n->r, (s + e) / 2, e);
    n->val = n->r->val + n->l->val;
}

int qry(int l, int r, pnode& n, int s = 0, int e = 2147483647){
    if(l >= e || r <= s) return 0;
    if(l <= s && e <= r) return n->val;
    push(n);
    prop(n, e - s);

    return qry(l, r, n->l, s, (s + e) / 2) + qry(l, r, n->r, (s + e) / 2, e);
}

int main()
{
    int m; cin >> m;
    int c = 0;
    pnode root = new node();
    for (int i = 0; i < m; i++) {
        int d, x, y; cin >> d >> x >> y;
        if(d == 1){
            int res = qry(x + c, y + c + 1, root);
            cout << res << "\n";
            c = res;
        }
        else{
            upd(x + c, y + c + 1, root);
        }
    }
    
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	18 ms	3416 KB	Output is correct
5	Correct	23 ms	4184 KB	Output is correct
6	Correct	22 ms	4188 KB	Output is correct
7	Correct	23 ms	4176 KB	Output is correct
8	Correct	149 ms	30572 KB	Output is correct
9	Correct	327 ms	51280 KB	Output is correct
10	Correct	339 ms	57956 KB	Output is correct
11	Correct	339 ms	62032 KB	Output is correct
12	Correct	327 ms	63824 KB	Output is correct
13	Correct	341 ms	74064 KB	Output is correct
14	Correct	316 ms	74832 KB	Output is correct
15	Correct	464 ms	136296 KB	Output is correct
16	Correct	445 ms	136836 KB	Output is correct
17	Correct	324 ms	77288 KB	Output is correct
18	Correct	332 ms	77368 KB	Output is correct
19	Correct	458 ms	139704 KB	Output is correct
20	Correct	451 ms	139852 KB	Output is correct