oj.uz

답안 #967402

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
967402 2024-04-22T04:57:59 Z irmuun 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 1357 ms 262144 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
    ll n;
    vector<ll>d;
    segtree(ll n):n(n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2]+d[node*2+1];
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l>R||r<L||L>R){
            return 0ll;
        }
        if(L<=l&&r<=R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k||r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll m;
    cin>>m;
    ll N=1e6;
    segtree sg(N);
    ll C=0;
    set<ll>st;
    for(ll i=1;i<=N+1;i++){
        st.insert(i);
    }
    for(ll i=1;i<=m;i++){
        ll t,l,r;
        cin>>t>>l>>r;
        l+=C;
        r+=C;
        if(t==2){
            vector<ll>v;
            auto it=st.lower_bound(l);
            while(*it<=r){
                ll x=*it;
                v.pb(x);
                sg.update(1,1,N,x,1);
                it++;
            }
            for(auto x:v){
                st.erase(x);
            }
        }
        else{
            C=sg.query(1,1,N,l,r);
            cout<<C<<"\n";
        }
    }
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 78496 KB Output is correct
2 Correct 185 ms 78584 KB Output is correct
3 Correct 184 ms 78800 KB Output is correct
4 Correct 377 ms 80792 KB Output is correct
5 Correct 421 ms 88016 KB Output is correct
6 Correct 350 ms 87768 KB Output is correct
7 Correct 402 ms 87192 KB Output is correct
8 Runtime error 1357 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -