oj.uz

답안 #967404

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
967404 2024-04-22T05:00:06 Z irmuun 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 2000 ms 194608 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{
    int n;
    vector<int>d;
    segtree(int n):n(n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(int node,int l,int r){
        if(l==r){
            d[node]=0;
            return;
        }
        int 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];
    }
    int query(int node,int l,int r,int L,int R){
        if(l>R||r<L||L>R){
            return 0ll;
        }
        if(L<=l&&r<=R){
            return d[node];
        }
        int mid=(l+r)/2;
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }
    void update(int node,int l,int r,int k,int val){
        if(l>k||r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        int 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);
    int m;
    cin>>m;
    int N=1e6;
    segtree sg(N);
    int C=0;
    set<int>st;
    for(int i=1;i<=N+1;i++){
        st.insert(i);
    }
    vector<int>v;
    int x;
    for(int i=1;i<=m;i++){
        int t,l,r;
        cin>>t>>l>>r;
        l+=C;
        r+=C;
        if(t==2){
            v.clear();
            auto it=st.lower_bound(l);
            while(*it<=r){
                x=*it;
                v.pb(x);
                sg.update(1,1,N,x,1);
                it++;
            }
            for(auto y:v){
                st.erase(y);
            }
        }
        else{
            C=sg.query(1,1,N,l,r);
            cout<<C<<"\n";
        }
    }
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 63060 KB Output is correct
2 Correct 181 ms 63092 KB Output is correct
3 Correct 180 ms 63060 KB Output is correct
4 Correct 373 ms 64228 KB Output is correct
5 Correct 406 ms 69068 KB Output is correct
6 Correct 343 ms 67000 KB Output is correct
7 Correct 429 ms 68300 KB Output is correct
8 Execution timed out 2037 ms 194608 KB Time limit exceeded
9 Halted 0 ms 0 KB -