Submission #49918

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49918	2018-06-05T01:19:29 Z	mra2322001	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	579 ms	150944 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].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){ /// 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:69:17: warning: unused variable 'x' [-Wunused-variable]
             int x = c;
                 ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	102 ms	138104 KB	Output is correct
2	Correct	102 ms	138104 KB	Output is correct
3	Correct	105 ms	138300 KB	Output is correct
4	Correct	123 ms	138328 KB	Output is correct
5	Correct	127 ms	138328 KB	Output is correct
6	Correct	122 ms	138368 KB	Output is correct
7	Correct	122 ms	138384 KB	Output is correct
8	Correct	297 ms	138572 KB	Output is correct
9	Correct	454 ms	138964 KB	Output is correct
10	Correct	448 ms	138964 KB	Output is correct
11	Correct	476 ms	138964 KB	Output is correct
12	Correct	449 ms	138964 KB	Output is correct
13	Correct	408 ms	138964 KB	Output is correct
14	Correct	433 ms	139148 KB	Output is correct
15	Correct	525 ms	139712 KB	Output is correct
16	Correct	579 ms	142168 KB	Output is correct
17	Correct	417 ms	144300 KB	Output is correct
18	Correct	488 ms	146484 KB	Output is correct
19	Correct	524 ms	148792 KB	Output is correct
20	Correct	526 ms	150944 KB	Output is correct