Submission #527121

#	Time	Username	Problem	Language	Result	Execution time	Memory
527121		8e7	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	184 ms	17680 KiB

event2

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct seg{
	int l, r, id;
	seg(){l = r = id = 0;}
	seg(int x, int y, int i){l = x, r = y, id = i;}
} a[maxn], b[maxn];
vector<int> val;
int anc[17][maxn];
int jump(int lind, int rig) {
	int ret = 0, cur = anc[0][lind];	
	if (b[cur].r > rig) return 0;
	ret = 1;
	for (int i = 16;i >= 0;i--) {
		if (b[anc[i][cur]].r <= rig) {
			ret += 1<<i;
			cur = anc[i][cur];
		}
	}
	return ret;	
}
int main() {
	io
	int n, k;
	cin >> n >> k;
	for (int i = 0;i < n;i++) {
		cin >> a[i].l >> a[i].r;
		a[i].id = i;
		val.push_back(a[i].l), val.push_back(a[i].r);
	}
	sort(val.begin(), val.end());
	val.resize(int(unique(val.begin(), val.end()) - val.begin()));
	for (int i = 0;i < n;i++) {
		a[i].l = lower_bound(val.begin(), val.end(), a[i].l) - val.begin();
		a[i].r = lower_bound(val.begin(), val.end(), a[i].r) - val.begin();
		b[i] = a[i];
	}	
	sort(a, a + n, [&] (seg x, seg y){return x.r > y.r;});
	priority_queue<pii, vector<pii>, less<pii> > pq;	
	int best = inf, bind = n;
	b[n] = seg(inf, inf, n);	
	for (int i = 0;i < n;i++) {
		while (pq.size() && pq.top().ff >= a[i].r) {
			if (b[pq.top().ss].r < best) {
				best = b[pq.top().ss].r;
				bind = pq.top().ss;
			}
			pq.pop();
		}
		anc[0][a[i].id] = bind;
		pq.push({a[i].l, a[i].id});
	}
	anc[0][n] = n;
	for (int i = 1;i < 17;i++) {
		for (int j = 0;j <= n;j++) anc[i][j] = anc[i-1][anc[i-1][j]]; 
	}	
	int lid = a[n-1].id;
	int ma = jump(lid, inf - 1) + 1;
	if (ma < k) {
		cout << -1 << endl;
		return 0;
	}
	set<pii> se;
	vector<int> ans;
	for (int i = 0;i < n;i++) {
		pii ins = {b[i].r, i};
		auto ind = se.lower_bound(ins);	
		bool inter = 0;
		int lef = 0, rig = 0, orig = 0;
		if (ind == se.end()) {
			rig = jump(i, inf - 1);	
		} else if (b[ind->ss].l < b[i].r) {
			inter = 1;
		} else {
			rig = jump(i, b[ind->ss].l);
		}
		if (ind == se.begin()) {
			orig++;
			if (b[i].r > a[n-1].r) {
				if (a[n-1].r > b[i].l) lef = 0;
				else lef = jump(lid, b[i].l) + 1;
			}	
		} else if (b[prev(ind)->ss].r > b[i].l) {
			inter = 1;
		} else {
			lef = jump(prev(ind)->ss, b[i].l);
		}
		debug(i, inter);
		if (inter) continue;
		orig += jump(ind == se.begin() ? lid : prev(ind)->ss, ind == se.end() ? inf - 1 : b[ind->ss].l);		
		debug(ma, orig, lef, rig);
		if (ma - orig + lef + rig + 1 >= k) {
			ans.push_back(i);
			se.insert(ins);
			ma = ma - orig + lef + rig + 1;
		}	
		if (ans.size() == k) break;
	}	
	for (int i:ans) cout << i+1 << "\n";
	
}
/*
7 4
1 3
2 5
6 9
3 4
5 7
8 10
10 11
*/

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
event2.cpp:108:3: note: in expansion of macro 'debug'
  108 |   debug(i, inter);
      |   ^~~~~
event2.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
event2.cpp:111:3: note: in expansion of macro 'debug'
  111 |   debug(ma, orig, lef, rig);
      |   ^~~~~
event2.cpp:117:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |   if (ans.size() == k) break;
      |       ~~~~~~~~~~~^~~~

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