oj.uz

Submission #673205

# Submission time Handle Problem Language Result Execution time Memory
673205 2022-12-19T22:23:07 Z US3RN4M3 Event Hopping (BOI22_events) C++17
0 / 100
 408 ms 32576 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 100005;
const int inf = 2e9;
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<<19); 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;
		}
		if(orig[e - 1].second > orig[s - 1].second) 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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6100 KB Output is correct
2 Correct 408 ms 26244 KB Output is correct
3 Correct 366 ms 32464 KB Output is correct
4 Correct 325 ms 32576 KB Output is correct
5 Correct 340 ms 31868 KB Output is correct
6 Correct 337 ms 31592 KB Output is correct
7 Correct 331 ms 31344 KB Output is correct
8 Correct 293 ms 26796 KB Output is correct
9 Correct 302 ms 26780 KB Output is correct
10 Correct 332 ms 25476 KB Output is correct
11 Incorrect 316 ms 24988 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6100 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 4 ms 6312 KB Output is correct
5 Incorrect 4 ms 6228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6100 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 4 ms 6312 KB Output is correct
5 Incorrect 4 ms 6228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6100 KB Output is correct
2 Correct 3 ms 6100 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 4 ms 6312 KB Output is correct
5 Incorrect 4 ms 6228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 26344 KB Output is correct
2 Correct 357 ms 32564 KB Output is correct
3 Correct 330 ms 32512 KB Output is correct
4 Correct 293 ms 26808 KB Output is correct
5 Correct 308 ms 25516 KB Output is correct
6 Incorrect 351 ms 24964 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6100 KB Output is correct
2 Correct 408 ms 26244 KB Output is correct
3 Correct 366 ms 32464 KB Output is correct
4 Correct 325 ms 32576 KB Output is correct
5 Correct 340 ms 31868 KB Output is correct
6 Correct 337 ms 31592 KB Output is correct
7 Correct 331 ms 31344 KB Output is correct
8 Correct 293 ms 26796 KB Output is correct
9 Correct 302 ms 26780 KB Output is correct
10 Correct 332 ms 25476 KB Output is correct
11 Incorrect 316 ms 24988 KB Output isn't correct
12 Halted 0 ms 0 KB -