Submission #967403

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
967403	2024-04-22T04:59:41 Z	irmuun	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	64300 KB

apple

#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){
            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

#	Verdict	Execution time	Memory	Grader output
1	Correct	185 ms	63060 KB	Output is correct
2	Correct	183 ms	63056 KB	Output is correct
3	Correct	180 ms	62908 KB	Output is correct
4	Execution timed out	2043 ms	64300 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-