Submission #967402

#	Time	Username	Problem	Language	Result	Execution time	Memory
967402		irmuun	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1357 ms	262144 KiB

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