Submission #537194

#	Time	Username	Problem	Language	Result	Execution time	Memory
537194		GioChkhaidze	Event Hopping 2 (JOI21_event2)	C++14	1 / 100	228 ms	40128 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;

bool check_add(int id) {
	int rpr = 0, lnx = 1e9, idn = 0, idp = 0;
	itl = stl.lower_bound({r[id], -1});
	itr = str.lower_bound({l[id], -1});
		
	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], -1});
	itr = str.lower_bound({l[id] + 1, -1});
	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;
	
	int res = getl(id, rpr) + 1 + getr(id, lnx);
	int resA = getl(idp, 0) + (idp != 0);
	int resB = getr(idn, 1e9) + (idn != 0);
	if (resA + res + resB >= k) return true;
	return false;
}

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)) {
			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:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main () {
      | ^~~~
event2.cpp: In function 'int main()':
event2.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (int i = 0; i < g.size(); ++i) {
      |                  ~~^~~~~~~~~~
event2.cpp:104: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]
  104 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~
event2.cpp:123:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |  if (res.size() < k) cout << -1 << "\n";
      |      ~~~~~~~~~~~^~~
event2.cpp:88:6: warning: unused variable 'sz' [-Wunused-variable]
   88 |  int sz = g.size();
      |      ^~

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