Submission #896683

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896683	2024-01-01T21:08:27 Z	raul2008487	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	330 ms	202832 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 int sz = 3e5+5; /// mind the sz
/*struct BIT{
    vl e;
    void init(ll n){
        e.assign(n+1, -1);
    }
    ll base(ll x){
        if(e[x] < 0){
            return x;
        }
        return e[x] = base(e[x]);
    }
    bool unite(ll a, ll b){
        a = base(a);
        b = base(b);
        if(a == b){return false;}
        if(e[a] > e[b]){swap(a, b);}
    }
};*/
struct Node{
    ll data = 0;
    Node *left = nullptr;
    Node *right = nullptr;
    bool ok = 0;
};
void update(ll tl, ll tr, ll l, ll r, Node *cur){
    if( tl > r || tr < l ){return ;}
    if(tl >= l && tr <= r){
        cur -> ok = 1;
        cur -> data = (tr - tl + 1);
        return ;
    }
    ll tm = (tl + tr)>>1;
    if(cur -> left == nullptr){
        cur -> left = new Node;
    }
    update(tl, tm, l, r, cur->left);
    if(cur -> right == nullptr){
        cur -> right = new Node;
    }
    update(tm+1, tr, l, r, cur->right);
    if(cur -> ok && cur -> data > 0){
        update(tl, tm, tl, tm, cur -> left);
        update(tm+1, tr, tm+1, tr, cur -> right);
    }
    cur -> data = (cur -> left -> data + cur -> right -> data);
}
ll get(ll tl, ll tr, ll l, ll r, Node *cur){
    if( tl > r || tr < l){
        return 0;
    }
    if(tl >= l && tr <= r){
        return (cur->data);
    }
    /*if( tl <= l && tr >= r && (cur -> data == (tr - tl + 1))){
        return (r - l + 1);
    }*/
    ll tm = (tl + tr) >> 1;
    if(cur -> ok && cur -> data > 0){
        if(cur -> left == nullptr){
            cur -> left = new Node;
        }
        update(tl, tm, tl, tm, cur -> left);
        if(cur -> right == nullptr){
            cur -> right = new Node;
        }
        update(tm + 1, tr, tm + 1, tr, cur -> right);
    }
    ll ret1 = 0, ret2 = 0;
    if(cur->left != nullptr){
        ret1 = get(tl, tm, l, r, cur->left);
    }
    if(cur->right != nullptr){
        ret2 = get(tm+1, tr, l, r, cur->right);
    }
    return ret1 + ret2;
}
void solve()
{
    ll m, i, j, l, r, type;
    ll n = 1, c = 0;
    while(n < 1e9){n <<= 1;}
    n <<= 1;
    cin>>m;
    Node *root = new Node;
    for(i=1;i<=m;i++){
        cin>>type>>l>>r;
        if(type == 1){
            ll ret = get(1, n, l + c, r + c, root);
            cout << ret << endl;
            c = ret;
        }
        else{
            update(1, n, l + c, r + c, root);
        }
    }

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

Compilation message

apple.cpp: In function 'void solve()':
apple.cpp:96:14: warning: unused variable 'j' [-Wunused-variable]
   96 |     ll m, i, j, l, r, type;
      |              ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	460 KB	Output is correct
4	Correct	9 ms	4752 KB	Output is correct
5	Correct	11 ms	5916 KB	Output is correct
6	Correct	11 ms	5724 KB	Output is correct
7	Correct	11 ms	5724 KB	Output is correct
8	Correct	87 ms	42836 KB	Output is correct
9	Correct	192 ms	76772 KB	Output is correct
10	Correct	226 ms	82004 KB	Output is correct
11	Correct	211 ms	88048 KB	Output is correct
12	Correct	202 ms	90716 KB	Output is correct
13	Correct	184 ms	107604 KB	Output is correct
14	Correct	185 ms	108628 KB	Output is correct
15	Correct	317 ms	196692 KB	Output is correct
16	Correct	313 ms	198048 KB	Output is correct
17	Correct	191 ms	112368 KB	Output is correct
18	Correct	187 ms	112248 KB	Output is correct
19	Correct	330 ms	202600 KB	Output is correct
20	Correct	324 ms	202832 KB	Output is correct