Submission #49915

#	Time	Username	Problem	Language	Result	Execution time	Memory
49915		mra2322001	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	18 ms	19328 KiB

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 = 1e6 + 2e5;
const int N = 1000000000;
struct node{
    int l, r, sum, add;
    node(){
        l = r = sum = add = 0;
    }
} t[NODE];

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 = x + get1(1, 1, N, u, v);
            cout << c - x << endl;
        }
        else up(1, 1, N, u, v);
    }
}

• Subtask 1: 0 / 100