Submission #1100054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100054		imarn	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	3 ms	4700 KiB

event2

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const ll inf=123456789,mxn=2e5+5;
int t[4*mxn]{0};
int sz=0;
int pr[mxn][20]{0};
void upd(int i,int amt){
    i+=sz;t[i]=max(t[i],amt);
    for(i>>=1;i;i>>=1)t[i]=max(t[2*i],t[2*i+1]);
}
int qr(int l,int r,int rs=0){
    for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
        if(l&1)rs=max(rs,t[l++]);
        if(r&1)rs=max(rs,t[--r]);
    }return rs;
}
int get(int l,int r,int rs=0){
    for(int j=19;j>=0;j--){
        if(pr[r][j]>l)rs+=1<<j,r=pr[r][j];
    }return (pr[r][0]>=l?rs+1:rs);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;vector<int>v;
    pii a[n],b[n];
    for(int i=0;i<n;i++)cin>>a[i].f>>a[i].s,v.pb(a[i].f),v.pb(a[i].s);
    sort(all(v));v.erase(unique(all(v)),v.end());
    for(int i=0;i<n;i++)a[i].f=lower_bound(all(v),a[i].f)-v.begin()+1,a[i].s=lower_bound(all(v),a[i].s)-v.begin()+1,b[i]=a[i];
    sort(b,b+n);sz=v.size()+1;int idx=0;
    for(int i=1;i<sz;i++){
        while(idx<n&&b[idx].f<=i)upd(b[idx].s,b[idx].f),idx++;
        pr[i][0]=qr(1,i+1);
    }for(int j=1;j<20;j++)for(int i=0;i<sz;i++)pr[i][j]=pr[pr[i][j-1]][j-1];
    multiset<pii>ms;ms.insert({1,sz-1});
    int res=get(1,sz-1);if(res<k){cout<<-1;return 0;}
    vector<int>ans;
    for(int i=0;i<n;i++){
        if(ans.size()==k)break;
        auto it = ms.upper_bound({a[i].f,0});
        if(it==ms.begin())continue;it--;
        if(it->s<a[i].s)continue;
        int rs1=get(a[i].f,a[i].s),rs2=get(it->f,a[i].f),rs3=get(a[i].s,it->s);
        if(res-rs1+rs2+rs3+1>=k){
            res=res-rs1+rs2+rs3+1;ans.pb(i+1);
            int l=it->f,r=it->s;ms.erase(it);
            if(l<a[i].f)ms.insert({l,a[i].f});
            if(a[i].s<r)ms.insert({a[i].s,r});
        }
    }for(int i=0;i<k;i++)cout<<ans[i]<<'\n';
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:49:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         if(ans.size()==k)break;
      |            ~~~~~~~~~~^~~
event2.cpp:51:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   51 |         if(it==ms.begin())continue;it--;
      |         ^~
event2.cpp:51:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   51 |         if(it==ms.begin())continue;it--;
      |                                    ^~

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