Submission #417210

#	Time	Username	Problem	Language	Result	Execution time	Memory
417210		shenxy	Event Hopping 2 (JOI21_event2)	C++11	39 / 100	586 ms	524292 KiB

event2

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
int dptable[100000];
vector<ii> events;
int dp(int i) {
	if (i == events.size()) return 0;
	if (dptable[i] != -1) return dptable[i];
	return dptable[i] = max(dp(i + 1), dp(lower_bound(events.begin(), events.end(), ii(events[i].second, 0)) - events.begin()) + 1);
}
int main() {
	int N, K;
	scanf("%d %d", &N, &K);
	int L[N], R[N];
	for (int i = 0; i < N; ++i) scanf("%d %d", &L[i], &R[i]);
	if (N <= 3000) {
		vector<int> ans;
		bool can_use[N];
		fill_n(can_use, N, true);
		for (int i = 0; i < N; ++i) {
			if (!can_use[i]) continue;
			events.clear();
			events.push_back(ii(L[i], R[i]));
			for (int j = i + 1; j < N; ++j) {
				if (can_use[j] && (R[i] <= L[j] || R[j] <= L[i])) events.push_back(ii(L[j], R[j]));
			}
			sort(events.begin(), events.end());
			fill_n(dptable, events.size(), -1);
			if (dp(0) + ans.size() >= K) {
				ans.push_back(i + 1);
				for (int j = i + 1; j < N; ++j) {
					if (L[j] < R[i] && L[i] < R[j]) can_use[j] = false;
				}
			}
		}
		if (ans.size() >= K) {
			for (int i = 0; i < K; ++i) printf("%d\n", ans[i]);
		} else printf("-1");
	} else {
		for (int i = 0; i < N; ++i) events.push_back(ii(L[i], R[i]));
		fill_n(dptable, events.size(), -1);
		if (dp(0) >= K) {
			int cur = 0, ptr = 0;
			while (cur < K) {
				while (cur + dp(lower_bound(events.begin(), events.end(), ii(events[ptr].second, 0)) - events.begin()) + 1 < K) ++ptr;
				printf("%d\n", ptr + 1);
				ptr = lower_bound(events.begin(), events.end(), ii(events[ptr].second, 0)) - events.begin(), ++cur;
			}
		} else printf("-1");
	}
	return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int dp(int)':
event2.cpp:9:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  if (i == events.size()) return 0;
      |      ~~^~~~~~~~~~~~~~~~
event2.cpp: In function 'int main()':
event2.cpp:31:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |    if (dp(0) + ans.size() >= K) {
      |        ~~~~~~~~~~~~~~~~~~~^~~~
event2.cpp:38:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   if (ans.size() >= K) {
      |       ~~~~~~~~~~~^~~~
event2.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d %d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~
event2.cpp:17:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  for (int i = 0; i < N; ++i) scanf("%d %d", &L[i], &R[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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