oj.uz

Submission #915880

# Submission time Handle Problem Language Result Execution time Memory
915880 2024-01-24T20:30:10 Z alexander707070 Event Hopping 2 (JOI21_event2) C++14
0 / 100
 3000 ms 32804 KB 
#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;

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<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;
    }

    poss.insert(0);
    poss.insert(cnt+1);

    all=howmany(1,cnt);

    for(int i=1;i<=n;i++){
        //auto it=poss.lower_bound(l[i]+1);
        //if(*it<r[i])continue;
        bool dali=false;
        for(int f=l[i]+1;f<=r[i]-1;f++){
            if(used[f]){
                dali=true; break;
            }
        }

        if(dali)continue;

        int mins=cnt+1,maxs=0;
        for(int f=l[i];f>=0;f--){
            if(used[f]){mins=f+1;break;}
        }
        for(int f=r[i];f<=cnt+1;f++){
            if(used[f]){maxs=f-1;break;}
        }

       // int maxs=*it-1; 
        //it--;
        //int mins=*it+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;

            for(int f=l[i];f<=r[i];f++){
                poss.insert(f);
                used[f]=true;
            }

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

    return 0;
}

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Execution timed out 3084 ms 32804 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Execution timed out 3084 ms 32804 KB Time limit exceeded
5 Halted 0 ms 0 KB -