oj.uz

답안 #1000923

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1000923 2024-06-18T11:24:34 Z ayankarimova 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
 2000 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll sz=6e6+6;
const ll mod=1e9+7;
ll st[sz], le[sz], re[sz], nxt=1, lazy[sz];
void relax(ll l, ll r, ll in)
{
    if(lazy[in]){
        st[in]=r-l+1;
        if(l!=r){
            if(!le[in]) le[in]=++nxt;
            if(!re[in]) re[in]=++nxt;
            lazy[le[in]]=1;
            lazy[re[in]]=1;
        }
        lazy[in]=0;
    }
}
void update(ll l, ll r, ll in, ll ql, ll qr)
{
    relax(l, r, in);
    if(ql>r || qr<l) return;
    if(ql<=l && r<=qr){
        st[in]=r-l+1;
        if(l!=r){
            if(!le[in]) le[in]=++nxt;
            if(!re[in]) re[in]=++nxt;
            lazy[le[in]]=1;
            lazy[re[in]]=1;
        }
        return;
    }
    ll mid=(l+r)/2;
    if(!le[in]) le[in]=++nxt;
    update(l, mid, le[in], ql, qr);
    if(!re[in]) re[in]=++nxt;
    update(mid+1, r, re[in], ql, qr);
    st[in]=st[le[in]]+st[re[in]];
}
ll res(ll l, ll r, ll in, ll ql, ll qr)
{
    relax(l, r, in);
    if(ql>r || qr<l) return 0;
    if(ql<=l && r<=qr) return st[in];
    ll mid=(l+r)/2;
    ll q1, q2;
    if(le[in]) q1=res(l, mid, le[in], ql, qr);
    else q1=0;
    if(re[in]) q2=res(mid+1, r, re[in], ql, qr);
    else q2=0;
    return q1+q2;
}
int main(){

    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll m;
    cin>>m;
    ll c=0;
    while(m--){
        ll t, a, b;
        cin>>t>>a>>b;
        if(t==2){
            a+=c; b+=c;
            update(1, 1e9, 1, a, b);
        }
        else{
            a+=c; b+=c;
            ll ans=res(1, 1e9, 1, a, b);
            cout<<ans<<endl;
            c=ans;
        }
    }
}
/*
{}[]
*/

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 8 ms 9564 KB Output is correct
5 Correct 9 ms 10076 KB Output is correct
6 Correct 9 ms 9820 KB Output is correct
7 Correct 9 ms 10124 KB Output is correct
8 Correct 75 ms 54868 KB Output is correct
9 Correct 170 ms 88656 KB Output is correct
10 Correct 173 ms 99424 KB Output is correct
11 Correct 170 ms 107684 KB Output is correct
12 Correct 182 ms 111440 KB Output is correct
13 Correct 161 ms 138332 KB Output is correct
14 Correct 158 ms 139604 KB Output is correct
15 Execution timed out 2328 ms 262144 KB Time limit exceeded
16 Halted 0 ms 0 KB -