Submission #49919

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49919	2018-06-05T01:21:26 Z	mra2322001	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	660 ms	139052 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){ /// 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:71: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	138064 KB	Output is correct
2	Correct	104 ms	138216 KB	Output is correct
3	Correct	111 ms	138292 KB	Output is correct
4	Correct	151 ms	138348 KB	Output is correct
5	Correct	131 ms	138452 KB	Output is correct
6	Correct	125 ms	138452 KB	Output is correct
7	Correct	129 ms	138452 KB	Output is correct
8	Correct	289 ms	138756 KB	Output is correct
9	Correct	528 ms	138756 KB	Output is correct
10	Correct	504 ms	138792 KB	Output is correct
11	Correct	477 ms	138996 KB	Output is correct
12	Correct	473 ms	138996 KB	Output is correct
13	Correct	438 ms	139036 KB	Output is correct
14	Correct	484 ms	139036 KB	Output is correct
15	Correct	660 ms	139036 KB	Output is correct
16	Correct	558 ms	139036 KB	Output is correct
17	Correct	471 ms	139036 KB	Output is correct
18	Correct	456 ms	139052 KB	Output is correct
19	Correct	602 ms	139052 KB	Output is correct
20	Correct	599 ms	139052 KB	Output is correct