Submission #888566

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888566	2023-12-17T19:43:55 Z	White	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	29 ms	15460 KB

apple

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

bitset<200000000>onlyOne,hasOne;

void update_tree(int l,int r,int L,int R,int now){
    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>=6 && r<=10){
        //cout<<l<<" _ "<<r<<": "<<hasOne[now]<<endl;
    }
    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,99999999,l,r,0);
        else {
            c=ans_tree(0,99999999,l,r,0);
            cout<<c<<endl;
        }
    }

    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	Output is correct
2	Correct	1 ms	8540 KB	Output is correct
3	Correct	1 ms	8540 KB	Output is correct
4	Correct	4 ms	8796 KB	Output is correct
5	Correct	5 ms	8796 KB	Output is correct
6	Correct	4 ms	8796 KB	Output is correct
7	Correct	4 ms	9048 KB	Output is correct
8	Correct	15 ms	13068 KB	Output is correct
9	Correct	29 ms	15460 KB	Output is correct
10	Correct	28 ms	15448 KB	Output is correct
11	Correct	29 ms	15336 KB	Output is correct
12	Correct	27 ms	15308 KB	Output is correct
13	Incorrect	23 ms	4956 KB	Output isn't correct
14	Halted	0 ms	0 KB	-