Submission #966825

#	Time	Username	Problem	Language	Result	Execution time	Memory
966825		Trisanu_Das	Event Hopping 2 (JOI21_event2)	C++17	39 / 100	630 ms	524288 KiB

event2

#include <bits/stdc++.h>
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; cin >> N >> K;
	int L[N], R[N];
	for (int i = 0; i < N; ++i) cin >> 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");
	}
}

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:30:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |    if (dp(0) + ans.size() >= K) {
      |        ~~~~~~~~~~~~~~~~~~~^~~~
event2.cpp:37:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |   if (ans.size() >= K)
      |       ~~~~~~~~~~~^~~~

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