Submission #1109139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109139		imarn	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	190 ms	27140 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 vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=2e5+5;
int t[2*mxn]{0};
int up[mxn][20]{0};
void upd(int i,int amt,int sz){
    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 sz,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 i=19;i>=0;i--){
        if(up[r][i]>l)r=up[r][i],rs+=1<<i;
    }
    return (up[r][0]==l?rs+1:rs);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    pii a[n],b[n];vector<int>vec;
    for(int i=0;i<n;i++)cin>>a[i].f>>a[i].s,vec.pb(a[i].f),vec.pb(a[i].s);
    sort(all(vec));vec.erase(unique(all(vec)),vec.end());
    for(int i=0;i<n;i++)a[i].f=lower_bound(all(vec),a[i].f)-vec.begin()+1,a[i].s=lower_bound(all(vec),a[i].s)-vec.begin()+1,b[i]=a[i];
    int m=vec.size();
    sort(b,b+n);int idx=0;
    for(int i=1;i<=m;i++){
        while(idx<n)upd(b[idx].s,b[idx].f,m+1),idx++;
        up[i][0]=qr(1,i+1,m+1);
    }
    for(int j=1;j<20;j++)for(int i=0;i<=m;i++)up[i][j]=up[up[i][j-1]][j-1];
    multiset<pii>ms;ms.insert({1,m});
    int rs=get(1,m);
    if(rs<k){
        cout<<-1;return 0;
    }vector<int>ans;
    for(int i=0;i<n;i++){
        auto it = ms.upper_bound({a[i].f,1e9});
        if(ans.size()==k)break;
        if(it==ms.begin())continue;
        it--;
        if(it->s<a[i].s)continue;
        if(rs-get(it->f,it->s)+1+get(it->f,a[i].f)+get(a[i].s,it->s)>=k){
            ans.pb(i+1);
            rs=rs-get(it->f,it->s)+1+get(it->f,a[i].f)+get(a[i].s,it->s);
            if(it->f<a[i].f)ms.insert({it->f,a[i].f});
            if(a[i].s<it->s)ms.insert({a[i].s,it->s});
            ms.erase(it);
        }
    }
    for(auto it : ans)cout<<it<<'\n';
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:55:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         if(ans.size()==k)break;
      |            ~~~~~~~~~~^~~

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