Submission #537175

#	Time	Username	Problem	Language	Result	Execution time	Memory
537175		GioChkhaidze	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	303 ms	41284 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], v[8 * N], L[N][19], R[N][19];

void upd(tree, int id, int vl, bool tp) {
	if (id < l || r < id) return ;
	if (l == id && id == r) {
		v[h] = vl;
		return ;
	}
	upd(left, id, vl, tp);
	upd(right, id, vl, tp);
	if (!tp) {
		if (v[lf]) v[h] = v[lf];
			else v[h] = v[rf];
	}
		else {
		if (v[rf]) v[h] = v[rf];
			else v[h] = v[lf];	
	}
}

int get(tree, int L, int R, int tp) {
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return v[h];
	int x = get(left, L, R, tp);
	int y = get(right, L, R, tp);
	if (!tp) {
		if (x) return x;	
		return y;
	}
		else {  
		if (y) return y;
		return x;	
	}
}

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, lnx, idn = 0, idp = 0;
	itl = stl.lower_bound({r[id], -1});
	itr = str.lower_bound({l[id], -1});
		
	if (itl == stl.end()) lnx = 1e9;
		else lnx = (*itl).f, idn = (*itl).s;		
		
	if (itr == str.begin()) rpr = 0;
		else --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]) 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});
	}
	
	sort(s.begin(), s.end());
	for (int i = s.size() - 1; i >= 0; --i) {
		if (s[i].f.s == 1) upd(1, 1, sz, r[s[i].s], s[i].s, 0);
			else
		if (s[i].f.s == 0) R[s[i].s][0] = get(1, 1, sz, r[s[i].s], sz, 0);
	}
	
	for (int i = 1; i <= 4 * sz; ++i) v[i] = 0;
	
	sort(s.begin(), s.end());
	for (int i = 0; i < s.size(); ++i) {
		if (s[i].f.s == 0) upd(1, 1, sz, l[s[i].s], s[i].s, 1);
			else
		if (s[i].f.s == 1) L[s[i].s][0] = get(1, 1, sz, 1, l[s[i].s], 1);
	}
	
	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:106:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  106 | main () {
      | ^~~~
event2.cpp: In function 'int main()':
event2.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for (int i = 0; i < g.size(); ++i) {
      |                  ~~^~~~~~~~~~
event2.cpp:141: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]
  141 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~
event2.cpp:161:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  161 |  if (res.size() < k) {
      |      ~~~~~~~~~~~^~~

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