Submission #1074720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074720		MOUF_MAHMALAT	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	152 ms	24100 KiB

event2

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
using namespace std;
typedef int ll;
typedef pair<ll,ll>pll;
const ll oo= 1e5+9;
ll n,k,dp[18][2*oo],sz;
pll a[oo],b[oo];
vector<ll>comp,ans;
ll go(ll l,ll r)
{
    ll mask=0;
    for(ll i=17; i>=0; i--)
        if(dp[i][l]<=r)
        {
            mask|=(1<<i);
            l=dp[i][l];
        }
    return mask;
}
void solve()
{
    cin>>n>>k;
    for(ll i=1; i<=n; i++)
    {
        cin>>a[i].F>>a[i].S;
        comp.push_back(a[i].F);
        comp.push_back(a[i].S);
    }
    sort(all(comp));
    comp.resize(unique(all(comp))-comp.begin());
    for(ll i=1; i<=n; i++)
    {
        a[i].F=lower_bound(all(comp),a[i].F)-comp.begin();
        a[i].S=lower_bound(all(comp),a[i].S)-comp.begin();
        b[i]=a[i];
    }
    sz=comp.size();
    sort(b+1,b+n+1);
    dp[0][sz]=sz;
    ll id=n;
    for(ll i=sz-1; i>=0; i--)
    {
        dp[0][i]=dp[0][i+1];
        while(id&&b[id].F>=i)
            dp[0][i]=min(dp[0][i],b[id].S),id--;
    }
    for(ll j=1; j<18; j++)
        for(ll i=0; i<=sz; i++)
            dp[j][i]=dp[j-1][dp[j-1][i]];
    set<pll>s;
    s.insert({0,0});
    s.insert({sz-1,sz-1});
    ll kk =go(0,sz-1);
    if(kk < k)
        return void(cout<<-1);
    for(ll i=1;i<=n;i++)
    {
        if(s.find(a[i])!=s.end())
            continue;
        s.insert(a[i]);
        auto it = s.find(a[i]);
        auto prev = it;prev--;
        auto next = it;next++;
        if(prev->S > it->F || it->S > next->F)
        {
            s.erase(a[i]);
            continue;
        }
        kk += go(prev->S,it->F) + go(it->S,next->F) - go(prev->S,next->F) +1;
        if(kk < k)
        {
            kk -= go(prev->S,it->F) + go(it->S,next->F) - go(prev->S,next->F) +1;
            s.erase(a[i]);
        }
        else
            ans.push_back(i);
        if(ans.size()==k)
            break;
    }
    for(auto&z:ans)
        cout<<z<<"\n";
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    ll tt=1;
//    cin>>tt;
    while(tt--)
        solve();
    return 0;
}

Compilation message (stderr)

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

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