Submission #915904

#	Time	Username	Problem	Language	Result	Execution time	Memory
915904		alexander707070	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	405 ms	36812 KiB

event2

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

const int inf=1e9;

int n,k,cnt,pt,ans,all;
int l[MAXN],r[MAXN],to[MAXN],ind[MAXN],beg[MAXN];

vector<int> w;
map<int,int> mp;
pair<int,int> e;

bool cmp(int x,int y){
    return r[x]<r[y];
}

bool cmp2(int x,int y){
    return l[x]<l[y];
}

int tree[4*MAXN];

int combine(int x,int y){
    if(r[x]<r[y])return x;
    return y;
}

void update(int v,int l,int r,int pos,int val){
    if(l==r){
        tree[v]=combine(tree[v],val);
    }else{
        int tt=(l+r)/2;
        if(pos<=tt)update(2*v,l,tt,pos,val);
        else update(2*v+1,tt+1,r,pos,val);

        tree[v]=combine(tree[2*v],tree[2*v+1]);
    }
}

int getmin(int v,int l,int r,int ll,int rr){
    if(ll>rr)return 0;
    if(l==ll and r==rr){
        return tree[v];
    }else{
        int tt=(l+r)/2;
        return combine( getmin(2*v,l,tt,ll,min(tt,rr)) , getmin(2*v+1,tt+1,rr,max(tt+1,ll),rr) );
    }
}

int dp[MAXN][20];
bool li[MAXN][20],used[MAXN];

int ff(int x,int p){
    if(p==0)return to[x];
    if(x==0)return 0;

    if(li[x][p])return dp[x][p];
    li[x][p]=true;

    dp[x][p]=ff(ff(x,p-1),p-1);
    return dp[x][p];
}

int howmany(int from,int to){
    int curr=beg[from],res=0;

    for(int i=19;i>=0;i--){
        if(r[ff(curr,i)]<=to){
            curr=ff(curr,i);
            res+=(1<<i);
        }
    }

    if(r[beg[from]]<=to)res++;
    return res;
}

set< pair<int,int> > poss;

int main(){

    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
        w.push_back(l[i]);
        w.push_back(r[i]);
    }

    sort(w.begin(),w.end());

    cnt=1;
    for(int i=0;i<w.size();i++){
        if(i>0 and w[i]!=w[i-1])cnt++;
        mp[w[i]]=cnt;
    }

    for(int i=1;i<=n;i++){
        l[i]=mp[l[i]];
        r[i]=mp[r[i]];
        ind[i]=i;
    }
    r[0]=inf;

    sort(ind+1,ind+n+1,cmp);

    for(int i=n;i>=1;i--){
        to[ind[i]]=getmin(1,1,cnt,r[ind[i]],cnt);
        update(1,1,cnt,l[ind[i]],ind[i]);   
    }
    for(int i=1;i<=4*cnt;i++)tree[i]=0;

    sort(ind+1,ind+n+1,cmp2);

    pt=n;
    for(int i=cnt;i>=1;i--){
        while(pt>=1 and l[ind[pt]]>=i){
            update(1,1,cnt,l[ind[pt]],ind[pt]);
            pt--;
        }

        beg[i]=getmin(1,1,cnt,i,cnt);
    }

    if(howmany(1,cnt)<k){
        cout<<"-1\n";
        return 0;
    }

    all=howmany(1,cnt);
    used[0]=used[cnt+1]=true;

    for(int i=1;i<=n;i++){
        auto it=poss.lower_bound({l[i],0});
        int mins,maxs;

        if(it!=poss.end()){
            e=*it;
            if(e.first<r[i])continue;
            maxs=e.first;
        }else{
            maxs=cnt;
        }

        if(!poss.empty() and it!=poss.begin()){
            it--;
            e=*it;
            if(e.second>l[i])continue;
            mins=e.second;
        }else{
            mins=1;
        }

        if(ans+1+all-howmany(mins,maxs)+howmany(mins,l[i])+howmany(r[i],maxs)>=k){
            cout<<i<<"\n";
            ans++;
            if(ans==k)return 0;

            poss.insert({l[i],r[i]});

            all=all-howmany(mins,maxs)+howmany(mins,l[i])+howmany(r[i],maxs);
        }
    }

    return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61