oj.uz

답안 #888566

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888566 2023-12-17T19:43:55 Z White 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
 29 ms 15460 KB 
#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

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