Submission #673199

#	Time	Username	Problem	Language	Result	Execution time	Memory
673199		US3RN4M3	Event Hopping (BOI22_events)	C++17	0 / 100	344 ms	32588 KiB

events

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 100005;
const int inf = 1e9;
int n, q;
pair<int, int> intervals[mx];
int ans[mx];
struct qd {
	set<pair<int, pair<int, int>>> qs;
	int cost;
	qd() {
		cost = 0;
	}
	void ins(pair<int, int> p) {
		qs.insert({p.first, {0, p.second}});
	}
	void merge(qd & oth) {
		int delta = oth.cost - cost;
		for(auto p : oth.qs) {
			qs.insert({p.first, {p.second.first + delta, p.second.second}});
		}
	}
	void sync(int i) {
		auto lim = qs.lower_bound({i + 1, {0, 0}});
		for(auto it = qs.begin(); it != lim; it = qs.erase(it)) {
			ans[it->second.second] = cost + it->second.first;
		}
	}
};
qd data0[mx];
struct st {
	pair<int, int> best;
	st * l;
	st * r;
	int size;
	st() {}
	st(int sz, int i) {
		size = sz;
		if(size > 1) {
			l = new st(size/2, i);
			r = new st((size + 1)/2, i + (size/2));
			best = max(l->best, r->best);
		} else {
			best = {intervals[i].second, i};
		}
	}
	pair<int, int> get(int s, int e) { /* [l, r) */
		s = max(0, s);
		e = min(e, size);
		if(s == 0 && e == size) return best;
		pair<int, int> res = {0, 0};
		if(s < l->size) res = max(res, l->get(s, e));
		if(e > l->size) res = max(res, r->get(s - l->size, e - l->size));
		return res;
	}
};
st tree;
int get_idx(int i) {
	int a = 0;
	for(int delta = (1<<18); delta >= 1; delta >>= 1) {
		int tmp = a + delta;
		if(tmp >= n) continue;
		if(intervals[tmp].first <= i) a = tmp;
	}
	return a;
}
main() {
	for(int i = 0; i < mx; i++) ans[i] = -1;
	cin >> n >> q;
	vector<pair<int, int>> orig(n);
	for(int i = 0; i < n; i++) {
		int s, e; cin >> s >> e;
		orig[i] = {s, e};
		intervals[i] = {inf - e, inf - s};
	}
	vector<pair<pair<int, int>, int>> order(n);
	for(int i = 0; i < n; i++) {
		order[i] = {{intervals[i].first, intervals[i].second}, i};
	}
	sort(order.begin(), order.end());
	vector<int> pos(n);
	for(int i = 0; i < n; i++) {
		pos[order[i].second] = i;
	}
	for(int i = 0; i < q; i++) {
		int s, e; cin >> e >> s;
		if(s == e) {
			ans[i] = 0;
			continue;
		}
		data0[pos[s - 1]].ins({intervals[e - 1].first, i});
	}
	vector<pair<int, int>> tmp(n);
	for(int i = 0; i < n; i++) {
		tmp[i] = intervals[order[i].second];
	}
	for(int i = 0; i < n; i++) {
		intervals[i] = tmp[i];
	}
	tree = st(n, 0);
	for(int i = 0; i < n; i++) {
		int r = intervals[i].second;
		int dst_int = get_idx(r);
		data0[i].cost++;
		data0[i].sync(r);
		if(dst_int == i) continue;
		pair<int, int> next_best = tree.get(i + 1, dst_int + 1);
		int nidx = next_best.second;
		if(data0[i].qs.size() > data0[nidx].qs.size()) swap(data0[i], data0[nidx]);
		data0[nidx].merge(data0[i]);
	}
	for(int i = 0; i < q; i++) {
		if(ans[i] == -1) cout << "impossible" << endl;
		else cout << ans[i] << endl;
	}
}

Compilation message (stderr)

events.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main() {
      | ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30