oj.uz

Submission #867721

# Submission time Handle Problem Language Result Execution time Memory
867721 2023-10-29T10:15:15 Z TAhmed33 Event Hopping (BOI22_events) C++
10 / 100
 416 ms 36688 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
int n, q;
vector <int> arr[MAXN];
vector <int> arr2[MAXN];
set <pair <int, int>> dd;
int par[MAXN];
int dep[MAXN], in[MAXN], out[MAXN];
int t = 0;
vector <int> adj[MAXN];
int val[MAXN];
void dfs (int pos) {
	in[pos] = ++t;
	for (auto j : adj[pos]) {
		dep[j] = 1 + dep[pos];
		dfs(j);
	}
	out[pos] = t;
}
bool flagged[MAXN]; int nxt[MAXN];
vector <vector <int>> events;
int main () {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		arr[i] = {l, r, i};
		events.push_back({l, 0, i});
		events.push_back({r, 1, i});
	}
	sort(events.begin(), events.end());
	reverse(events.begin(), events.end());
	while (!events.empty()) {
		int u = events.back()[0];
		vector <vector <int>> k;
		while (!events.empty() && events.back()[0] == u) {
			k.push_back(events.back());
			events.pop_back();
		}
		sort(k.begin(), k.end());
		reverse(k.begin(), k.end());
		while (!k.empty() && k.back()[1] == 0) {
			dd.insert({arr[k.back()[2]][1], k.back()[2]});
			k.pop_back();
		}
		vector <pair <int, int>> removals;
		while (!k.empty()) {
			dd.erase({k.back()[0], k.back()[2]});
			auto g = dd.lower_bound({k.back()[0], 0});
			if (g == dd.end()) {
				par[k.back()[2]] = -1;
				k.pop_back();
				continue;
			}
			par[k.back()[2]] = (*g).second;
			dd.insert({k.back()[0], k.back()[2]});
			k.pop_back();
		}
		for (auto i : removals) dd.erase(i);
	}
	for (int i = 1; i <= n; i++) {
		if (par[i] != -1 && par[par[i]] == i) {
			if (arr[par[i]][0] <= arr[i][0]) {
				flagged[i] = 1; nxt[i] = par[i];
			} else {
				flagged[par[i]] = 1; nxt[par[i]] = i;
			}
			par[par[i]] = -1; par[i] = -1; 
		}
	}
	for (int i = 1; i <= n; i++) if (par[i] != -1) {
		adj[par[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) if (par[i] == -1) dfs(i);
	while (q--) {
		int a, b;
		cin >> a >> b;
		if (a == b) {
			cout << "0\n";
			continue;
		}
		int ansss = 0; 
		if (flagged[a]) {
			a = nxt[a]; ansss++;
		}
		if (flagged[b]) {
			b = nxt[b]; ansss++;
		}
		if (a == b) {
			cout << ansss << '\n';
			continue;
		}
		if (arr[a][1] == arr[b][1]) {
			cout << ansss + 1 << '\n';
			continue;
		}
		if (in[a] > in[b] && out[a] <= out[b]) {
			cout << ansss + dep[a] - dep[b] << '\n';
		} else {
			cout << "impossible\n";
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 320 ms 35604 KB Output is correct
3 Correct 330 ms 35320 KB Output is correct
4 Correct 335 ms 35260 KB Output is correct
5 Correct 328 ms 35316 KB Output is correct
6 Correct 320 ms 34592 KB Output is correct
7 Correct 333 ms 34544 KB Output is correct
8 Correct 311 ms 29964 KB Output is correct
9 Correct 288 ms 27892 KB Output is correct
10 Correct 329 ms 34124 KB Output is correct
11 Correct 331 ms 31744 KB Output is correct
12 Correct 258 ms 27640 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 36452 KB Output is correct
2 Correct 324 ms 35828 KB Output is correct
3 Correct 416 ms 36688 KB Output is correct
4 Correct 272 ms 29172 KB Output is correct
5 Correct 323 ms 33268 KB Output is correct
6 Incorrect 354 ms 36636 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 320 ms 35604 KB Output is correct
3 Correct 330 ms 35320 KB Output is correct
4 Correct 335 ms 35260 KB Output is correct
5 Correct 328 ms 35316 KB Output is correct
6 Correct 320 ms 34592 KB Output is correct
7 Correct 333 ms 34544 KB Output is correct
8 Correct 311 ms 29964 KB Output is correct
9 Correct 288 ms 27892 KB Output is correct
10 Correct 329 ms 34124 KB Output is correct
11 Correct 331 ms 31744 KB Output is correct
12 Correct 258 ms 27640 KB Output is correct
13 Incorrect 2 ms 9564 KB Output isn't correct
14 Halted 0 ms 0 KB -