Submission #49920

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49920	2018-06-05T01:22:27 Z	mra2322001	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	601 ms	139140 KB

apple

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)

using namespace std;
typedef long long ll;
const int NODE = 2e6 + 2e5;
const int N = 1000000000;
struct node{
    int l, r, sum, add;
    node(){
        l = r = sum = add = 0;
    }
} t[NODE*4];

int c, cnt = 1;

void push(int k, int l, int r){
    if(t[k].l==0) t[k].l = ++cnt;
        if(t[k].r==0) t[k].r = ++cnt;
    if(t[k].add){
        if(t[k].l==0) t[k].l = ++cnt;
        if(t[k].r==0) t[k].r = ++cnt;
        t[t[k].l].add = 1;
        t[t[k].r].add = 1;
        t[k].sum = (r - l + 1);
        t[k].add = 0;
    }
}

void up(int k, int l, int r, int u, int v){
    push(k, l, r);
    if(r < u || l > v) return ;
    if(l >= u && r <= v){
        t[k].add = 1;
        t[k].sum = (r - l + 1);
        return ;
    }
    int m = (l + r)/2;
    if(t[k].l==0) t[k].l = ++cnt;
    if(t[k].r==0) t[k].r = ++cnt;
    up(t[k].l, l, m, u, v);
    up(t[k].r, m + 1, r, u, v);
    t[k].sum = t[t[k].l].sum + t[t[k].r].sum;
}

int get1(int k, int l, int r, int u, int v){
    push(k, l, r);
    if(r < u || l > v) return 0;
    if(l >= u && r <= v) return t[k].sum;
    int m = (l + r)/2;
    int res = 0;
    if(t[k].l==0) t[k].l = ++cnt;
        if(t[k].r==0) t[k].r = ++cnt;
    if(t[k].l){ /// neu khong co t[k].l thi nghia la no chua duoc update(de len tao chin do) lan nao ca => res = 0 khong can suy nghi, vi
        /// lam the moi tiet kiem duoc bo nho
        res += (get1(t[k].l, l, m, u, v));
    }
    if(t[k].r){
        res += get1(t[k].r, m + 1, r, u, v);
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
  
    int m; cin >> m;
    while(m--){
        int ty, u, v; cin >> ty >> u >> v;
        u += c, v += c;
        if(ty==1){
            int x = c;
            c = get1(1, 1, N, u, v);
            cout << c << endl;
        }
        else up(1, 1, N, u, v);
    }
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:73:17: warning: unused variable 'x' [-Wunused-variable]
             int x = c;
                 ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	138284 KB	Output is correct
2	Correct	103 ms	138336 KB	Output is correct
3	Correct	105 ms	138336 KB	Output is correct
4	Correct	155 ms	138336 KB	Output is correct
5	Correct	139 ms	138464 KB	Output is correct
6	Correct	138 ms	138464 KB	Output is correct
7	Correct	134 ms	138464 KB	Output is correct
8	Correct	306 ms	138484 KB	Output is correct
9	Correct	521 ms	138808 KB	Output is correct
10	Correct	565 ms	138808 KB	Output is correct
11	Correct	515 ms	138808 KB	Output is correct
12	Correct	524 ms	139036 KB	Output is correct
13	Correct	427 ms	139036 KB	Output is correct
14	Correct	445 ms	139036 KB	Output is correct
15	Correct	565 ms	139140 KB	Output is correct
16	Correct	601 ms	139140 KB	Output is correct
17	Correct	435 ms	139140 KB	Output is correct
18	Correct	460 ms	139140 KB	Output is correct
19	Correct	555 ms	139140 KB	Output is correct
20	Correct	577 ms	139140 KB	Output is correct