Submission #40358

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
40358	2018-01-31T11:35:29 Z	TAMREF	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	58 ms	28184 KB

apple

#include <bits/stdc++.h>
using namespace std;

namespace DynamicSegtree{
    int st, en, n, d, x, y;
    struct node{
        int v, s, e;
        node *l, *r;
        node() {}
        node(int v, int s, int e):v(v),s(s),e(e),l(0),r(0) {}
        void update(){
            if(s > en || e < st) return;
            if(v == e - s + 1) return;
            if(st <= s && e <= en){
                v = e - s + 1; return;
            }
            int m = (s+e)/2;
            if(!l) l = new node(0,s,m);
            if(!r) r = new node(0,m+1,e);

            l->update();
            r->update();

            v = l->v + r->v;
        }
        int query(){
            if(s > en || e < st) return 0;
            if(v == e - s + 1){
                return min(e,en) - max(s,st) + 1;
            }
            if(st <= s && e <= en) return v;
            int m = (s+e)/2;
            if(!l) l = new node(0,s,m);
            if(!r) r = new node(0,m+1,e);
            return l->query() + r->query();
        }
    };
}
using namespace DynamicSegtree;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n, c = 0;
    node *root = new node(0,1,1<<30);
    cin >> n;
    for(int ty; n--; ){
        cin >> ty >> st >> en;
        st += c; en += c;
        if(ty == 1){
            c = root->query();
            cout << c << '\n';
        }else{
            root->update();
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	1 ms	356 KB	Output is correct
3	Correct	2 ms	412 KB	Output is correct
4	Correct	5 ms	648 KB	Output is correct
5	Correct	6 ms	800 KB	Output is correct
6	Correct	11 ms	1096 KB	Output is correct
7	Correct	11 ms	1244 KB	Output is correct
8	Correct	27 ms	2448 KB	Output is correct
9	Correct	44 ms	4492 KB	Output is correct
10	Correct	46 ms	6592 KB	Output is correct
11	Correct	45 ms	8200 KB	Output is correct
12	Correct	45 ms	10204 KB	Output is correct
13	Correct	50 ms	12344 KB	Output is correct
14	Correct	49 ms	14512 KB	Output is correct
15	Correct	58 ms	17084 KB	Output is correct
16	Correct	45 ms	19236 KB	Output is correct
17	Correct	51 ms	21324 KB	Output is correct
18	Correct	50 ms	23632 KB	Output is correct
19	Correct	43 ms	25848 KB	Output is correct
20	Correct	42 ms	28184 KB	Output is correct