Submission #911314

#	Time	Username	Problem	Language	Result	Execution time	Memory
911314		Tuanlinh123	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	193 ms	73676 KiB

event2

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=200005;
ll l[maxn], r[maxn], sp[20][maxn*2];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, k; cin >> n >> k;
    vector <ll> num;
    for (ll i=1; i<=n; i++)
    {
        cin >> l[i] >> r[i];
        num.pb(l[i]); num.pb(r[i]);
    }
    sort(num.begin(), num.end());
    num.resize(unique(num.begin(), num.end())-num.begin());
    ll s=num.size();
    for (ll i=1; i<=s+1; i++) sp[0][i]=s+1;
    for (ll i=1; i<=n; i++)
    {
        l[i]=lower_bound(num.begin(), num.end(), l[i])-num.begin()+1;
        r[i]=lower_bound(num.begin(), num.end(), r[i])-num.begin()+1;
        sp[0][l[i]]=min(sp[0][l[i]], r[i]);
    }
    for (ll i=s; i>=1; i--)
        sp[0][i]=min(sp[0][i], sp[0][i+1]);
    for (ll i=1; i<20; i++)
        for (ll j=1; j<=s+1; j++)
            sp[i][j]=sp[i-1][sp[i-1][j]];
    auto query=[&](ll l, ll r)
    {
        ll ans=0, crr=l;
        for (ll i=19; i>=0; i--)
            if (sp[i][crr]<=r)
                ans+=1<<i, crr=sp[i][crr];
        return ans;
    };
    ll cnt=query(1, s);
    if (cnt<k) {cout << -1; exit(0);}
    vector <ll> ans;
    set <pll> S; S.insert(mp(1, s));
    for (ll i=1; i<=n; i++)
    {
        auto it=S.lower_bound(mp(l[i], s+1));
        if (it==S.begin()) continue; it--;
        ll L, R; tie(L, R)=*it;
        if (R<r[i]) continue;
        ll lose=query(L, R)-(query(L, l[i])+query(r[i], R)+1);
        if (cnt-lose<k) continue;
        S.erase(it), cnt-=lose;
        if (L<l[i]) S.insert(mp(L, l[i]));
        if (r[i]<R) S.insert(mp(r[i], R));
        ans.pb(i); if (ans.size()==k) break;
    }
    for (ll i:ans) cout << i << "\n";
}

Compilation message (stderr)

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

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