Submission #1063814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063814		TrinhKhanhDung	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	189 ms	159572 KiB

apple

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

struct Node{
    int val, lazy, l, r;
    Node(){
        val = 0;
        lazy = -1;
        l = -1;
        r = -1;
    }
};

const int lim = 1e7 + 10;

int timer;
Node nodes[lim];

int newNode(){
    return ++timer;
}

void push(int i, int l, int r){
    if(nodes[i].l == -1) nodes[i].l = newNode();
    if(nodes[i].r == -1) nodes[i].r = newNode();
    if(nodes[i].lazy == -1) return;
    int L = nodes[i].l, R = nodes[i].r;
    nodes[L].lazy = nodes[i].lazy;
    nodes[R].lazy = nodes[i].lazy;
    int m = (l + r) >> 1;
    nodes[L].val = nodes[i].lazy * (m - l + 1);
    nodes[R].val = nodes[i].lazy * (r - m);
    nodes[i].lazy = -1;
}

void update(int i, int l, int r, int u, int v, int c){
    if(i == -1) i = newNode();
    if(r < u || v < l) return;
    if(u <= l && r <= v){
        nodes[i].lazy = c;
        nodes[i].val = c * (r - l + 1);
        return;
    }
    push(i, l, r);
    int m = (l + r) >> 1;
    update(nodes[i].l, l, m, u, v, c);
    update(nodes[i].r, m + 1, r, u, v, c);
    nodes[i].val = nodes[nodes[i].l].val + nodes[nodes[i].r].val;
}

int getVal(int i, int l, int r, int u, int v){
    if(i == -1 || r < u || v < l) return 0;
    if(u <= l && r <= v) return nodes[i].val;
    push(i, l, r);
    int m = (l + r) >> 1;
    int L = getVal(nodes[i].l, l, m, u, v);
    int R = getVal(nodes[i].r, m + 1, r, u, v);
    return L + R;
}

void solve(){
    int q; cin >> q;
    int c = 0;
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;

        if(t == 1){
            int ans = getVal(0, 1, (int)1e9, l + c, r + c);
            cout << ans << '\n';
            c = ans;
        }
        else{
            update(0, 1, (int)1e9, l + c, r + c, 1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("terrorists.inp", "r", stdin);
//    freopen("terrorists.out", "w", stdout);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

• Subtask 1: 100 / 100