oj.uz

Submission #867729

# Submission time Handle Problem Language Result Execution time Memory
867729 2023-10-29T10:25:11 Z TAhmed33 Event Hopping (BOI22_events) C++
10 / 100
 351 ms 35180 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();
		}
		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 328 ms 34964 KB Output is correct
3 Correct 329 ms 34376 KB Output is correct
4 Correct 350 ms 34548 KB Output is correct
5 Correct 323 ms 34012 KB Output is correct
6 Correct 327 ms 33332 KB Output is correct
7 Correct 351 ms 32544 KB Output is correct
8 Correct 327 ms 28404 KB Output is correct
9 Correct 273 ms 27324 KB Output is correct
10 Correct 333 ms 31996 KB Output is correct
11 Correct 327 ms 30312 KB Output is correct
12 Correct 257 ms 26620 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 324 ms 35180 KB Output is correct
2 Correct 344 ms 35048 KB Output is correct
3 Correct 338 ms 34148 KB Output is correct
4 Correct 286 ms 27828 KB Output is correct
5 Correct 331 ms 32664 KB Output is correct
6 Incorrect 349 ms 34424 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 328 ms 34964 KB Output is correct
3 Correct 329 ms 34376 KB Output is correct
4 Correct 350 ms 34548 KB Output is correct
5 Correct 323 ms 34012 KB Output is correct
6 Correct 327 ms 33332 KB Output is correct
7 Correct 351 ms 32544 KB Output is correct
8 Correct 327 ms 28404 KB Output is correct
9 Correct 273 ms 27324 KB Output is correct
10 Correct 333 ms 31996 KB Output is correct
11 Correct 327 ms 30312 KB Output is correct
12 Correct 257 ms 26620 KB Output is correct
13 Incorrect 2 ms 9564 KB Output isn't correct
14 Halted 0 ms 0 KB -