답안 #896678

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896678 2024-01-01T21:03:21 Z raul2008487 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
1 ms 348 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 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -