Submission #919890

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919890	2024-02-01T19:26:07 Z	raul2008487	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	464 ms	232784 KB

apple

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
//#define endl "\n"
using namespace std;
const int mod = 998244353;
const long long inf = 1000000000000000000;
const int sz = 3e5+5; /// mind the sz
ll L[80*sz], R[80*sz], st[80*sz], lazy[80*sz], cur = 1;
void ms(ll v){
    if(!L[v]){L[v] = ++cur;}
    if(!R[v]){R[v] = ++cur;}
}
void relax(ll v, ll l, ll r){
    if(!lazy[v]){return ;}
    st[v] = (r - l + 1);
    if(l == r){
        lazy[v] = 0;
        return ;
    }
    ms(v);
    lazy[L[v]] += lazy[v];
    lazy[R[v]] += lazy[v];
    lazy[v] = 0;
}
void update(ll v, ll tl, ll tr, ll l, ll r){
    relax(v, tl, tr);
    if(tl > r or tr < l){return ;}
    if(tl >= l && tr <= r){
        lazy[v] = 1;
        relax(v, tl, tr);
        return ;
    }
    ll tm = (tl + tr) >> 1;
    if(tm < l){
        if(!R[v]){R[v] = ++cur;}
        update(R[v], tm+1, tr, l, r);
    }
    else if(tm >= r){
        if(!L[v]){L[v] = ++cur;}
        update(L[v], tl, tm, l, r);
    }
    else{
        ms(v);
        update(L[v], tl, tm, l, r);
        update(R[v], tm+1, tr, l, r);
    }
    relax(L[v], tl, tm);
    relax(R[v], tm+1, tr);
    st[v] = st[L[v]] + st[R[v]];
}
ll get(ll v, ll tl, ll tr, ll l, ll r){
    relax(v, tl, tr);
    if(tl > r || tr < l){return 0;}
    if(tl >= l && tr <= r){
        return st[v];
    }
    ll tm = (tl + tr) >> 1;
    if(tm < l){
        if(!R[v]){R[v] = ++cur;}
        return get(R[v], tm+1, tr, l, r);
    }
    else if(tm >= r){
        if(!L[v]){L[v] = ++cur;}
        return get(L[v], tl, tm, l, r);
    }
    else{
        ms(v);
        return get(L[v], tl, tm, l, r) + get(R[v], tm+1, tr, l, r);
    }
}
void solve(){
    ll q, i, j, l, r, x, c = 0, qt, n = 1e9;
    cin>>q;
    while(q--){
        cin>>qt>>l>>r;
        l += c;
        r += c;
        if(qt == 1){
            ll res = get(1, 1, n, l, r);
            c = res;
            cout << res << endl;
        }
        else{
            update(1, 1, n, l, r);
        }
    }

}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //precomp();
    ll tst=1;
    //cin>>tst;
    while(tst--){
        solve();
    }
}
/*
3
2 5 8
2 7 10
1 1 10
ok.
*/

Compilation message

apple.cpp: In function 'void solve()':
apple.cpp:83:11: warning: unused variable 'i' [-Wunused-variable]
   83 |     ll q, i, j, l, r, x, c = 0, qt, n = 1e9;
      |           ^
apple.cpp:83:14: warning: unused variable 'j' [-Wunused-variable]
   83 |     ll q, i, j, l, r, x, c = 0, qt, n = 1e9;
      |              ^
apple.cpp:83:23: warning: unused variable 'x' [-Wunused-variable]
   83 |     ll q, i, j, l, r, x, c = 0, qt, n = 1e9;
      |                       ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2392 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	16 ms	8280 KB	Output is correct
5	Correct	19 ms	9808 KB	Output is correct
6	Correct	20 ms	9560 KB	Output is correct
7	Correct	18 ms	9556 KB	Output is correct
8	Correct	143 ms	49500 KB	Output is correct
9	Correct	320 ms	83280 KB	Output is correct
10	Correct	331 ms	91984 KB	Output is correct
11	Correct	368 ms	98888 KB	Output is correct
12	Correct	352 ms	101480 KB	Output is correct
13	Correct	299 ms	123688 KB	Output is correct
14	Correct	307 ms	125488 KB	Output is correct
15	Correct	464 ms	226492 KB	Output is correct
16	Correct	447 ms	228176 KB	Output is correct
17	Correct	292 ms	129616 KB	Output is correct
18	Correct	303 ms	129616 KB	Output is correct
19	Correct	457 ms	231964 KB	Output is correct
20	Correct	446 ms	232784 KB	Output is correct