Submission #417782

#	Time	Username	Problem	Language	Result	Execution time	Memory
417782		maomao90	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	247 ms	31048 KiB

event2

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 200005
#define MAXL 25

struct range {
	int l, r, i;
	bool operator< (const range& o) const {
		return l < o.l;
	}
};

int n, k;
ii lr[MAXN];
range ranges[MAXN];
queue<range> q;
int p[MAXL][MAXN];
set<range> st;
vi ans;

bool in(ii l, ii r) {
	if (l.FI <= r.FI && l.SE > r.FI) {
		return 1;
	}
	swap(l, r);
	if (l.FI <= r.FI && l.SE > r.FI) {
		return 1;
	}
	return 0;
}

int jump(int i, int l) {
	int res = 0;
	RREP (k, MAXL - 1, 0) {
		if (p[k][i] != -1 && lr[p[k][i]].SE <= l) {
			res += (1 << k);
			i = p[k][i];
		}
	}
	return res;
}

int main() {
	scanf("%d%d", &n, &k);
	REP (i, 2, n + 2) {
		scanf("%d%d", &lr[i].FI, &lr[i].SE);
	}
	lr[0] = MP(0, 1); lr[1] = MP(INF, INF + 1);
	n += 2;
	REP (i, 0, n) {
		ranges[i] = {lr[i].FI, lr[i].SE, i};
	}
	sort(ranges, ranges + n, [&] (range l, range r) {
			return l.r < r.r;
			});
	memset(p, -1, sizeof p);
	REP (i, 0, n) {
		while (!q.empty() && q.front().r <= ranges[i].l) {
			p[0][q.front().i] = ranges[i].i;
			//printf("%d -> %d\n", q.front().i, ranges[i].i);
			q.pop();
		}
		q.push(ranges[i]);
	}
	REP (k, 1, MAXL) {
		REP (i, 0, n) {
			if (p[k - 1][i] == -1) continue;
			p[k][i] = p[k - 1][p[k - 1][i]];
		}
	}
	st.insert(ranges[0]); st.insert(ranges[n - 1]);
	int cur = jump(0, ranges[n - 1].l);
	REP (i, 2, n) {
		if (ans.size() == k) break;
		auto [l, r] = lr[i];
		auto nxt = st.lower_bound({l, -1, -1});
		auto prv = prev(nxt);
		if (in(MP(nxt -> l, nxt -> r), lr[i]) || 
				in(MP(prv -> l, prv -> r), lr[i])) {
			continue;
		}
		int tmp = cur;
		tmp -= jump(prv -> i, nxt -> l);
		int lft = jump(i, nxt -> l), rht = jump(prv -> i, l);
		tmp += lft + rht + 1;
		//printf("%d: %d %d\n", i, tmp, k);
		if (tmp >= k) {
			cur = tmp;
			st.insert({l, r, i});
			ans.pb(i);
		}
	}
	if (ans.empty()) {
		printf("-1\n");
	} else {
		for (int i : ans) {
			printf("%d\n", i - 1);
		}
	}
	return 0;
}

/*
4 2
1 4
3 5
4 9
7 10

12 3
1 4
1 8
1 3
1 2
1 4
3 8
3 5
3 9
6 11
6 10
6 12
6 7

6 3
1 7
2 5
2 4
4 8
4 7
8 9

6 4
1 3
1 2
2 4
4 5
5 6
6 7
*/

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:99:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |   if (ans.size() == k) break;
      |       ~~~~~~~~~~~^~~~
event2.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
event2.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d%d", &lr[i].FI, &lr[i].SE);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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