Submission #49921

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49921	2018-06-05T01:31:45 Z	mra2322001	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	649 ms	139056 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);
        /// bat buoc vi gia su khi l >= u && r <= v ma truoc do ta chua up t[k].sum thi no se return t(l, r) ma chua tinh t[k] hien tai
        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:74:17: warning: unused variable 'x' [-Wunused-variable]
             int x = c;
                 ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	118 ms	138104 KB	Output is correct
2	Correct	108 ms	138104 KB	Output is correct
3	Correct	104 ms	138136 KB	Output is correct
4	Correct	133 ms	138220 KB	Output is correct
5	Correct	152 ms	138340 KB	Output is correct
6	Correct	130 ms	138416 KB	Output is correct
7	Correct	140 ms	138416 KB	Output is correct
8	Correct	327 ms	138588 KB	Output is correct
9	Correct	591 ms	138776 KB	Output is correct
10	Correct	532 ms	138828 KB	Output is correct
11	Correct	523 ms	138912 KB	Output is correct
12	Correct	547 ms	138924 KB	Output is correct
13	Correct	510 ms	138924 KB	Output is correct
14	Correct	517 ms	139052 KB	Output is correct
15	Correct	649 ms	139052 KB	Output is correct
16	Correct	640 ms	139052 KB	Output is correct
17	Correct	476 ms	139052 KB	Output is correct
18	Correct	514 ms	139052 KB	Output is correct
19	Correct	613 ms	139052 KB	Output is correct
20	Correct	566 ms	139056 KB	Output is correct