Submission #440736

#	Time	Username	Problem	Language	Result	Execution time	Memory
440736		leaked	Segments (IZhO18_segments)	C++14	100 / 100	3061 ms	12620 KiB

segments

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC opimize(-O3)
//#pragma GCC opimize(Ofast)
//#pragma GCC opimize(unroll-loops)
//#pragma GCC target("avx,avx2,popcnt,sse,sse2,sse3,sse4,abm,tune=native")
#define m_p make_pair
#define vec vector
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define f first
#define s second

using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef pair<int,int> pii;
const int K=2000;
const int B=K;
const int N=2e5+4;
template <class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int l[N],r[N];
bool used[N];
struct mine{
    vec<pii>ls;
    vec<pii>fck;vec<pii>fck2;
    vec<pii>nw;
    vec<int>st1[N/K+1];vec<int>st[N/K+1];
    void build(){
        for(int i=0;i<=(sz(ls)-1)/K;i++){
            st[i].clear();st1[i].clear();
        }
        for(int i=0;i<sz(ls);i++){
            st[i/K].pb(r[ls[i].s]-l[ls[i].s]+1);
            st1[i/K].pb(r[ls[i].s]);
        }
        for(int i=0;i<=(sz(ls)-1)/K;i++){
            sort(all(st[i]));
            sort(all(st1[i]));
        }
    }
    void add(int i){
        fck.pb({l[i],i});
        if(sz(fck)==K){
            for(auto &z : fck) ls.pb(z);
            fck.clear();sort(all(ls));
            build();
        }
    }
    void del(int i){
//        cout<<"BLYA"<<endl;
        fck2.pb({l[i],i});
        used[i]=1;
//        assert(sz(fck2)==1);
        if(sz(fck2)==K){
            assert(!sz(nw));
            for(auto &z : fck) ls.pb(z);
            fck.clear();sort(all(ls));
            for(auto &z : ls){
                if(!used[z.s]){
                    nw.pb(z);
//                    cerr<<"ALO "<<z.f<<' '<<z.s<<endl;
                }
            }
            swap(ls,nw);nw.clear();fck2.clear();
            build();
        }
    }
    int fnd(int x){
        int id=lower_bound(all(ls),m_p(x,-2))-ls.begin();
        return id;
    }
    int get1(int l1,int r1,int x){
        int ans=0;
        for(int i=l1/K;i<=r1/K;i++){
            int l2=i*B,r2=l2+B-1;
            if(l2>=l1 && r2<=r1){
                int lung=lower_bound(all(st1[i]),x)-st1[i].begin();
                ans+=B-lung;
            }
            else{
                l2=max(l1,l2);r2=min(r1,r2);
                for(int j=l2;j<=r2;j++){
                    int id=ls[j].s;
                    ans+=(r[id]>=x);
                }
            }
        }
        return ans;
    }
    int get(int l1,int r1,int x){
        int ans=0;
        for(int i=l1/K;i<=r1/K;i++){
            int l2=i*B,r2=l2+B-1;
            if(l2>=l1 && r2<=r1){
                int lung=lower_bound(all(st[i]),x)-st[i].begin();
                ans+=B-lung;
            }
            else{
                l2=max(l1,l2);r2=min(r1,r2);
                for(int j=l2;j<=r2;j++){
                    int id=ls[j].s;
                    ans+=((r[id]-l[id]+1)>=x);
                }
            }
        }
        return ans;
    }
}kek;
int u=1;
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int q,t;
    cin>>q>>t;
    ///fuck this shit
    int lstans=0;
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            int a,b;
            cin>>a>>b;
            a=(a^(lstans*t));
            b=(b^(lstans*t));
            if(a>b) swap(a,b);
            l[u]=a;r[u]=b;
            kek.add(u);
            u++;
        }
        else if(tp==2){
            int id;
            cin>>id;
            kek.del(id);
        }
        else{
            int a,b,k;
            cin>>a>>b>>k;
            a=(a^(lstans*t));
            b=(b^(lstans*t));
            if(a>b) swap(a,b);
            if(b-a+1<k){
                lstans=0;
                cout<<0<<'\n';
                continue;
            }
            int lf=a,rt=b;
            int l1=kek.fnd(lf),r1=kek.fnd(rt-k+2)-1;
            int ans=kek.get(l1,r1,k);
            ans+=kek.get1(0,l1-1,k+lf-1);
            for(auto &z : kek.fck){
                if(z.f>=lf && z.f<=(rt-k+1) && r[z.s]-l[z.s]+1>=k) ans++;
                else if(z.f<lf && r[z.s]>=k+lf-1) ans++;
            }
            for(auto &z : kek.fck2){
                if(z.f>=lf && z.f<=(rt-k+1) && r[z.s]-l[z.s]+1>=k) ans--;
                else if(z.f<lf && r[z.s]>=k+lf-1) ans--;
            }
            cout<<ans<<'\n';
            lstans=ans;
        }
    }
    return 0;
}
/*
5 1
1 1 2
1 3 5
3 2 3 1
2 1
3 0 3 1

*/

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 25 / 25