Submission #1170756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170756		monkey133	Event Hopping 2 (JOI21_event2)	C++20	39 / 100	261 ms	46932 KiB

event2

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
#pragma GCC optimize("O3","unroll-loops")
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll const INF = 1e15;
ll n, k;
ll l[100005], r[100005], twok[500005][25];
vector<ll> dis;
vector<pi> sorted;

ll calc(ll l, ll r)
{
	ll ans = 0;
	for (ll k=19; k>=0; --k) if (twok[l][k] <= r) {l = twok[l][k]; ans += (1LL << k);}
	if (twok[l][0] == r + 1) ans++;
	return ans;
}

int main()
{
	cin >> n >> k;
	for (ll i=0; i<n; ++i) {cin >> l[i] >> r[i]; r[i]--; dis.pb(l[i]); dis.pb(r[i]);}
	discretize(dis);
	for (ll i=0; i<n;++i)
	{
		l[i] = lb(all(dis), l[i])-dis.begin();
		r[i] = lb(all(dis), r[i])-dis.begin();
		sorted.pb(mp(l[i], r[i]));
	}
	discretize(dis);
	ll m = dis.size();
	//for (ll i=0; i<m; ++i) show(dis[i]);
	//show(3);
	sort(all(sorted), greater<pi> ());
	ll idx = 0, mn = m;
	for (ll i=m-1; i>=0; --i)
	{
		while (idx < n && sorted[idx].f >= i)
		{
			mn = min(mn, sorted[idx].s);
			idx++;
		}
		twok[i][0] = mn + 1;
		//show(twok[i][0]);
		
	}
	//show(2);
	for (ll k=1; k<20; ++k)
	{
		for (ll j=0; j<m; ++j)
		{
			if (twok[j][k-1]>= m) twok[j][k] = twok[j][k-1];
			else twok[j][k] = twok[twok[j][k-1]][k-1];
		}
	}
	//show(1);
	set<pi> ss; ss.insert(mp(0, m-1));
	ll maxk = calc(0, m-1);
	//show(maxk);
	if (maxk < k) {cout << "-1\n"; return 0;}
	vector<ll> ans;
	for (ll i=0; i<n; ++i)
	{
		//show(i);
		auto it = ss.ub(mp(l[i], INF));
		if (it!=ss.begin()) it--;
		else {continue;}
		if (it->f > l[i] || it->s < r[i]) {continue;}
		ll dk = calc(it->f, l[i]-1) + calc(r[i]+1, it->s) + 1 - calc(it->f, it->s);
		if (maxk + dk < k){continue;}
		maxk += dk;
		ll x = it->f, y = it->s;
		ss.erase(it);
		if (x <= l[i]-1) ss.insert(mp(x, l[i]-1));
		if (y >= r[i] + 1) ss.insert(mp(r[i] + 1, y));
		ans.pb(i + 1);
		//for (pi u: ss) show2(u.f, u.s);
	}
	if (ans.size() < k) {cout << "-1\n"; return 0;}
	for (ll i=0; i<k; ++i) cout << ans[i] << endl;
	return 0;
}

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