Submission #442969

#	Time	Username	Problem	Language	Result	Execution time	Memory
442969		ics0503	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	271 ms	24288 KiB

event2

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
struct xy {
	int x, y;
}a[121212];
int all[212121], alln = 0;
int ST[212121][20];
int get_cnt(int l, int r) {
	int now = l, i, cnt = 0;
	for (i = 19; i >= 0; i--) {
		if (ST[now][i] <= r) {
			cnt += (1 << i);
			now = ST[now][i];
		}
	}
	return cnt;
}
set<pair<int, int>>S;
int main() {
	int n, k; scanf("%d%d", &n, &k);
	int i, j;
	for (i = 0; i < n; i++) {
		scanf("%d%d", &a[i].x, &a[i].y);
		all[alln++] = a[i].x;
		all[alln++] = a[i].y;
	}
	sort(all, all + alln);
	alln = unique(all, all + alln) - all;
	for (i = 0; i < n; i++) a[i] = { lower_bound(all,all + alln,a[i].x) - all,lower_bound(all,all + alln,a[i].y) - all };
	for (i = 0; i <= alln; i++) {
		for (j = 0; j < 20; j++) {
			ST[i][j] = 1e9;
		}
	}
	for (i = 0; i < n; i++) {
		ST[a[i].x][0] = min(ST[a[i].x][0], a[i].y);
	}
	for (i = alln - 2; i >= 0; i--) ST[i][0] = min(ST[i + 1][0], ST[i][0]);
	for (j = 1; j < 20; j++) {
		for (i = 0; i < alln; i++) {
			if (ST[i][j - 1] > alln)continue;
			ST[i][j] = ST[ST[i][j - 1]][j - 1];
		}
		for (i = alln - 2; i >= 0; i--) ST[i][j] = min(ST[i + 1][j], ST[i][j]);
	}
	int X = get_cnt(0, alln - 1);
	if (X < k) {
		puts("-1");
		return 0;
	}
	S.insert({ -0,alln - 1 });
	int acnt = 0;
	for (i = 0; i < n; i++) {
		auto it = S.lower_bound({ -a[i].x,a[i].y });
		auto l = -(it->first), r = it->second;
		if (r < a[i].y)continue;
		int ls = l, le = a[i].x;
		int rs = a[i].y, re = r;
		int x = get_cnt(l, r);
		int y = get_cnt(ls, le);
		int z = get_cnt(rs, re);
		if (X - x + y + z + 1 >= k) {
			S.erase(it);
			S.insert({ -ls, le });
			S.insert({ -rs,re });
			X = X - x + y + z + 1;
			printf("%d\n", i + 1);
			acnt++;
			if (acnt == k)break;
		}
	}
	return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:31:70: warning: narrowing conversion of '((std::lower_bound<int*, int>(((int*)(& all)), (((int*)(& all)) + ((sizetype)(((long unsigned int)alln) * 4))), a[i].xy::x) - ((int*)(& all))) <unknown operator> 4)' from 'long int' to 'int' [-Wnarrowing]
   31 |  for (i = 0; i < n; i++) a[i] = { lower_bound(all,all + alln,a[i].x) - all,lower_bound(all,all + alln,a[i].y) - all };
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
event2.cpp:31:111: warning: narrowing conversion of '((std::lower_bound<int*, int>(((int*)(& all)), (((int*)(& all)) + ((sizetype)(((long unsigned int)alln) * 4))), a[i].xy::y) - ((int*)(& all))) <unknown operator> 4)' from 'long int' to 'int' [-Wnarrowing]
   31 |  for (i = 0; i < n; i++) a[i] = { lower_bound(all,all + alln,a[i].x) - all,lower_bound(all,all + alln,a[i].y) - all };
      |                                                                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
event2.cpp:22:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  int n, k; scanf("%d%d", &n, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~
event2.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d%d", &a[i].x, &a[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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