Submission #1063814

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063814	2024-08-18T03:38:05 Z	TrinhKhanhDung	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	189 ms	159572 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	156752 KB	Output is correct
2	Correct	54 ms	156880 KB	Output is correct
3	Correct	56 ms	156880 KB	Output is correct
4	Correct	59 ms	157008 KB	Output is correct
5	Correct	62 ms	157132 KB	Output is correct
6	Correct	61 ms	157048 KB	Output is correct
7	Correct	62 ms	157008 KB	Output is correct
8	Correct	104 ms	158048 KB	Output is correct
9	Correct	161 ms	158904 KB	Output is correct
10	Correct	150 ms	158968 KB	Output is correct
11	Correct	158 ms	159060 KB	Output is correct
12	Correct	168 ms	159000 KB	Output is correct
13	Correct	150 ms	159520 KB	Output is correct
14	Correct	156 ms	159312 KB	Output is correct
15	Correct	177 ms	159528 KB	Output is correct
16	Correct	174 ms	159568 KB	Output is correct
17	Correct	149 ms	159344 KB	Output is correct
18	Correct	163 ms	159572 KB	Output is correct
19	Correct	189 ms	159572 KB	Output is correct
20	Correct	177 ms	159568 KB	Output is correct