oj.uz

답안 #919890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919890 2024-02-01T19:26:07 Z raul2008487 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 464 ms 232784 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 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

# 결과 실행 시간 메모리 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