Submission #537724

#	Time	Username	Problem	Language	Result	Execution time	Memory
537724		GioChkhaidze	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	454 ms	38768 KiB

event2

#include <bits/stdc++.h>

#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define pb push_back
#define f first
#define s second

using namespace std;

const int N = 1e5 + 5;

int n, k;
int l[N], r[N], ans[N], L[N][19], R[N][19];

int getl(int idx, int rpr) {
	int ret = 0;
	if (!idx) return ret;
	for (int j = 17; j >= 0; --j) {
		if (!L[idx][j]) continue;
		if (rpr <= l[L[idx][j]]) {
			ret += (1 << j);
			idx = L[idx][j];
		}
	}
	return ret;
}

int getr(int idx, int lnx) {
	int ret = 0;
	if (!idx) return ret;
	for (int j = 17; j >= 0; --j) {
		if (!R[idx][j]) continue;
		if (r[R[idx][j]] <= lnx) {
			ret += (1 << j);
			idx = R[idx][j];
		}
	}
	return ret;
}

vector < int > res;
set < pair < int , int > > stl, str;
set < pair < int , int > > :: iterator itl, itr;

int tot, resA, resB;
bool check_add(int id) {
	int res, resA, resB, rpr = 0, lnx = 1e9, idn = 0, idp = 0;
	if (!stl.size()) {
		res = getl(id, 0) + 1 + getr(id, 1e9);
		if (res >= k) {
			tot = res;
			return true;
		}
		return false;
	}

	itl = stl.lower_bound({r[id], 0});
	itr = str.lower_bound({l[id] + 1, 0});
		
	if (itl != stl.end()) lnx = (*itl).f, idn = (*itl).s;		
	if (itr != str.begin()) --itr, rpr = (*itr).f, idp = (*itr).s;
		
	itl = stl.lower_bound({l[id], 0});
	itr = str.lower_bound({l[id] + 1, 0});
	
	if (itl != stl.end() && l[(*itl).s] < r[id]) return false;
	if (itr != str.end() && (r[(*itr).s] <= r[id] || l[(*itr).s] <= l[id])) return false;
	
	res = getl(id, rpr) + 1 + getr(id, lnx);
	if (idp) {
		resA = getr(idp, lnx);
		if (tot - resA + res >= k) {
			tot -= resA - res;
			return true;
		}
		return false;
	}
	if (idn) {
		resB = getl(idn, rpr);
		if (tot - resB + res >= k) {
			tot -= resB - res;
			return true;
		}
		return false;
	}
	res += 1/0;
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> k;
	vector < pair < pair < int , int > , int > > s; 
	map < int , int > f;
	vector < int > g;
	for (int i = 1; i <= n; ++i) {
		cin >> l[i] >> r[i];
		g.pb(l[i]), g.pb(r[i]);	
	}
	
	sort(g.begin(), g.end());
	g.erase(unique(g.begin(), g.end()), g.end());
	for (int i = 0; i < g.size(); ++i) {
		f[g[i]] = i + 1;
	}
	
	int sz = g.size();
	for (int i = 1; i <= n; ++i) {
		l[i] = f[l[i]], r[i] = f[r[i]];
		s.pb({{l[i], 1}, i});
		s.pb({{r[i], 0}, i});
	}
	
	int rm = 1e9, idr = 0;
	sort(s.begin(), s.end());
	for (int i = s.size() - 1; i >= 0; --i) {
		int id = s[i].s, tp = s[i].f.s;
		if (tp && r[id] < rm) rm = r[id], idr = id;
		if (!tp) R[id][0] = idr;
	}
	
	int lm = 0, idl = 0;
	for (int i = 0; i < s.size(); ++i) {
		int id = s[i].s, tp = s[i].f.s;
		if (!tp && lm < l[id]) lm = l[id], idl = id;
		if (tp) L[id][0] = idl;
	}
	
	for (int j = 1; j <= 17; ++j)
		for (int i = 1; i <= n; ++i) {
			L[i][j] = L[L[i][j - 1]][j - 1];
			R[i][j] = R[R[i][j - 1]][j - 1];
		}

	for (int i = 1; i <= n; ++i) 
		if (check_add(i) && res.size() < k) {
			stl.insert({l[i], i});
			str.insert({r[i], i});
			res.pb(i);
		}
	
	if (res.size() < k) cout << -1 << "\n";
		else {
		for (int i = 0; i < k; ++i) 
			cout << res[i] << "\n";
	}
}

Compilation message (stderr)

event2.cpp: In function 'bool check_add(int)':
event2.cpp:91:10: warning: division by zero [-Wdiv-by-zero]
   91 |  res += 1/0;
      |         ~^~
event2.cpp: At global scope:
event2.cpp:94:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   94 | main () {
      | ^~~~
event2.cpp: In function 'int main()':
event2.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for (int i = 0; i < g.size(); ++i) {
      |                  ~~^~~~~~~~~~
event2.cpp:128:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~
event2.cpp:141:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  141 |   if (check_add(i) && res.size() < k) {
      |                       ~~~~~~~~~~~^~~
event2.cpp:147:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  147 |  if (res.size() < k) cout << -1 << "\n";
      |      ~~~~~~~~~~~^~~
event2.cpp:112:6: warning: unused variable 'sz' [-Wunused-variable]
  112 |  int sz = g.size();
      |      ^~
event2.cpp: In function 'bool check_add(int)':
event2.cpp:91:6: warning: control reaches end of non-void function [-Wreturn-type]
   91 |  res += 1/0;
      |  ~~~~^~~~~~

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