답안 #896683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896683 2024-01-01T21:08:27 Z raul2008487 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
330 ms 202832 KB
#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;
      |              ^
# 결과 실행 시간 메모리 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