Submission #970528

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
970528	2024-04-26T16:31:48 Z	islam998	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	358 ms	235936 KB

apple

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define nots0fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define vl vector<ll>
#define pll pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define in insert
#define all(v) v.begin(), v.end()
#define mid(a, b) ((a) + (b)) / 2
using namespace std;
mt19937 rng(time(NULL)); // rng()%(r - l + 1) + l

const int MX = 1e5 + 5 , inf = 1e9 + 99, sz = 5005, mod = 1000000007, N = 1e6 + 31, MOD = 998244353;
const ll INF = 100000000000000007;

ll sg[MX * 80], lz[MX * 80], L[MX * 80], R[MX * 80], last = 1;

void check(ll node){
    if(!L[node]){
        L[node] = ++last;
    }
    if(!R[node]){
        R[node] = ++last;
    }
}

void relax(ll k, ll l, ll r){
    if(!lz[k]) return ;
    sg[k] = (r - l + 1);
    if(l == r){
        lz[k] = 0;
        return ;
    }
    check(k);
    lz[L[k]] += lz[k];
    lz[R[k]] += lz[k];
    lz[k] = 0;
}

void update(ll k, ll a, ll b, ll l, ll r){
    relax(k, a, b);
    if(l > b || r < a){
        return ;
    }
    if(l <= a && r >= b){
        lz[k]++;
        relax(k, a, b);
        return ;
    }
    int mid = mid(a, b);
    if (l > mid){
        if (!R[k]) R[k] = ++last;
        update(R[k], mid + 1, b, l, r);
    }
    else if (r <= mid){
        if (!L[k]) L[k] = ++last;
        update(L[k], a, mid, l, r);
    }
    else{
        check(k);
        update(L[k], a, mid, l, r);
        update(R[k], mid + 1, b, l, r);
    }
    relax(L[k], a, mid);
    relax(R[k], mid + 1, b);
    sg[k] = sg[L[k]] + sg[R[k]];
}

ll get(ll k, ll a, ll b, ll l, ll r){
    relax(k, a, b);
    if(l > b || r < a){
        return 0;
    }
    if(l <= a && r >= b){
        return sg[k];
    }
    int mid = mid(a, b);
    if (l > mid){
        if (!R[k]) R[k] = ++last;
        return get(R[k], mid + 1, b, l, r);
    }
    else if (r <= mid){
        if (!L[k]) L[k] = ++last;
        return get(L[k], a, mid, l, r);
    }
    check(k);
    return get(L[k], a, mid, l, r) + get(R[k], mid + 1, b, l, r);
}

void solve () {
    ll q, n = 1e9, plus = 0, res = 0;
    cin >> q;    
    while(q--){
        ll type, l, r;
        cin >> type >> l >> r;
        l += plus;
        r += plus;
        if(type == 1){
            res = get(1, 1, n, l, r);
            plus = res;
            cout << res << endl;
        }
        else{
            update(1, 1, n, l, r);
        }
    }
}

signed main(){
    nots0fast
    int test = 1;
    for(int tst = 1; tst <= test; tst++) {
        solve();
        cout << endl;
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	12 ms	10332 KB	Output is correct
5	Correct	14 ms	11868 KB	Output is correct
6	Correct	14 ms	11612 KB	Output is correct
7	Correct	14 ms	11864 KB	Output is correct
8	Correct	119 ms	52448 KB	Output is correct
9	Correct	243 ms	86936 KB	Output is correct
10	Correct	242 ms	95724 KB	Output is correct
11	Correct	262 ms	100644 KB	Output is correct
12	Correct	251 ms	104120 KB	Output is correct
13	Correct	216 ms	125520 KB	Output is correct
14	Correct	214 ms	127572 KB	Output is correct
15	Correct	343 ms	227924 KB	Output is correct
16	Correct	358 ms	230480 KB	Output is correct
17	Correct	227 ms	132152 KB	Output is correct
18	Correct	214 ms	132180 KB	Output is correct
19	Correct	343 ms	234832 KB	Output is correct
20	Correct	345 ms	235936 KB	Output is correct