oj.uz

Submission #888573

# Submission time Handle Problem Language Result Execution time Memory
888573 2023-12-17T20:27:46 Z White Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 160 ms 83728 KB 
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

bitset<2000000000>onlyOne,hasOne;

void update_tree(int l,int r,int L,int R,int now){
    //cout<<now<<" "<<l<<" "<<r<<endl;
    if(l>R || r<L || onlyOne[now]==1)return ;
    if(l>=L && r<=R){
        onlyOne[now]=1;
        hasOne[now]=1;
        return;
    }
    int mid=(l+r)/2;
    update_tree(l,mid,L,R,now*2+1);
    update_tree(mid+1,r,L,R,now*2+2);
    if(onlyOne[now*2+1]==1 && onlyOne[now*2+2]==1)onlyOne[now]=1;
    if(hasOne[now*2+1]==1 || hasOne[now*2+2]==1 || onlyOne[now*2+2]==1 || onlyOne[now*2+1]==1)hasOne[now]=1;
}

int ans_tree(int l,int r,int L,int R,int now){
    if(l>R || r<L || hasOne[now]==0)return 0;
    if(onlyOne[now]==1){
        //cout<<l<<" )_( "<<r<<endl;
        return (min(r,R)-max(l,L)+1);
    }
    int mid=(l+r)/2;
    return ans_tree(l,mid,L,R,now*2+1)+ans_tree(mid+1,r,L,R,now*2+2);
}

int main(){

    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    int n,c=0;
    cin>>n;
    for(int t=0;t<n;t++){
        int l,r,type;
        cin>>type>>l>>r;
        l--;r--;
        l+=c;
        r+=c;
        //cout<<l<<"-"<<r<<endl;
        if(type==2)update_tree(0,999999999,l,r,0);
        else {
            c=ans_tree(0,999999999,l,r,0);
            cout<<c<<endl;
        }
    }

    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 12 ms 15028 KB Output is correct
5 Correct 14 ms 14936 KB Output is correct
6 Correct 15 ms 14996 KB Output is correct
7 Correct 15 ms 14940 KB Output is correct
8 Correct 64 ms 19284 KB Output is correct
9 Correct 125 ms 19280 KB Output is correct
10 Correct 128 ms 22136 KB Output is correct
11 Correct 128 ms 21336 KB Output is correct
12 Correct 142 ms 21396 KB Output is correct
13 Correct 160 ms 40020 KB Output is correct
14 Correct 135 ms 25684 KB Output is correct
15 Correct 138 ms 56660 KB Output is correct
16 Correct 146 ms 83728 KB Output is correct
17 Runtime error 21 ms 29772 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -