Submission #478957

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
478957	2021-10-09T08:29:23 Z	MohammadAghil	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	452 ms	207624 KB

apple

#include <bits/stdc++.h> 
using  namespace std;
typedef  long long ll;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 
 
const ll mod = 998244353, maxn = 2e6 + 5, inf = 1e9 + 5;

struct Node{
    Node *l, *r;
    int lx, rx;
    int sum, lazy;
    Node(int lx, int rx): lx(lx), rx(rx){
        sum = 0, lazy = 0;
        l = r = NULL;
    }
} *root;

void pull(Node *x){
    x->lazy = 1;
    x->sum = x->rx - x->lx;
}

void shift(Node *x){
    int mid = (x->lx + x->rx) >> 1;
    if(!x->l) {
        x->l = new Node(x->lx, mid);
    }
    if(!x->r) x->r = new Node(mid, x->rx);
    if(x->lazy){
        pull(x->l); 
        pull(x->r);
    }
    x->lazy = 0;
}

void upd(int l, int r, Node *x = root){
    if(l <= x->lx && r >= x->rx){
        pull(x);
        return;
    }
    if(l >= x->rx || r <= x->lx) return;
    shift(x);
    upd(l, r, x->l);
    upd(l, r, x->r);
    x->sum = x->l->sum + x->r->sum;
}

int query(int l, int r, Node *x = root){
    if(l <= x->lx && r >= x->rx) return x->sum;
    if(l >= x->rx || r <= x->lx) return 0;
    shift(x);
    return query(l, r, x->l) + query(l, r, x->r); 
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    root = new Node(0, inf);
    int q; cin >> q;
    int c = 0;
    while(q--){
        int d, l, r; cin >> d >> l >> r;
        if(d == 1){
            c = query(c + l, c + r + 1);
            cout << c << '\n';
        }else upd(c + l, c + r + 1);
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	16 ms	4964 KB	Output is correct
5	Correct	17 ms	5948 KB	Output is correct
6	Correct	20 ms	5800 KB	Output is correct
7	Correct	17 ms	5972 KB	Output is correct
8	Correct	146 ms	44440 KB	Output is correct
9	Correct	291 ms	77212 KB	Output is correct
10	Correct	302 ms	85316 KB	Output is correct
11	Correct	297 ms	91680 KB	Output is correct
12	Correct	296 ms	94396 KB	Output is correct
13	Correct	257 ms	109920 KB	Output is correct
14	Correct	261 ms	111004 KB	Output is correct
15	Correct	451 ms	201700 KB	Output is correct
16	Correct	452 ms	203252 KB	Output is correct
17	Correct	288 ms	114756 KB	Output is correct
18	Correct	276 ms	114840 KB	Output is correct
19	Correct	442 ms	207624 KB	Output is correct
20	Correct	450 ms	207536 KB	Output is correct