oj.uz

Submission #867733

# Submission time Handle Problem Language Result Execution time Memory
867733 2023-10-29T10:49:51 Z TAhmed33 Event Hopping (BOI22_events) C++
10 / 100
 1500 ms 18020 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int bad = 1e9;
struct SegmentTree {
	int tree[2 * MAXN];
	void init () {
		for (auto &i : tree) i = bad;
	}
	void update (int l, int r, int a, int b, int node) {
		if (l > a || r < a) return;
		if (l == r) {
			tree[node] = min(tree[node], b);
			return;
		}
		update(l, mid, a, b, tl);
		update(mid + 1, r, a, b, tr);
		tree[node] = min(tree[tl], tree[tr]);
	}
	int get (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return bad;
		if (l >= a && r <= b) return tree[node];
		return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
} cur;
vector <int> adj[MAXN];
vector <int> arr[MAXN];
vector <int> d;
int dp[MAXN];
vector <vector <int>> events;
int main () {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		arr[i] = {l, r, i};
		d.push_back(l); d.push_back(r);
	}
	sort(d.begin(), d.end()); d.resize(unique(d.begin(), d.end()) - d.begin());
	for (int i = 1; i <= n; i++) {
		arr[i][0] = lower_bound(d.begin(), d.end(), arr[i][0]) - d.begin();
		arr[i][1] = lower_bound(d.begin(), d.end(), arr[i][1]) - d.begin();
		arr[i][0]++; arr[i][1]++;
	}
	sort(arr + 1, arr + n + 1, [] (vector <int> &a, vector <int> &b) {
		return a[1] == b[1] ? a[0] < b[0] : a[1] < b[1];
	});
	while (q--) {	
		int a, b;
		cin >> a >> b; 
		if (a == b) {
			cout << "0\n";
			continue;
		}
		cur.init();
		int ans = -1;
		for (int i = 1; i <= n; i++) {
			int l = arr[i][0], r = arr[i][1], idx = arr[i][2];
			if (idx == a) {
				cur.update(1, MAXN, r, 0, 1);
				continue;
			}
			if (idx == b) {
				ans = cur.get(1, MAXN, l, r, 1);
				break;
			}
			int x = cur.get(1, MAXN, l, r, 1);
			cur.update(1, MAXN, r, x + 1, 1);
		}		
		ans++;
		if (ans > n) {
			cout << "impossible\n";
		} else {
			cout << ans << '\n';
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11868 KB Output is correct
2 Execution timed out 1592 ms 15900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11868 KB Output is correct
2 Correct 3 ms 11868 KB Output is correct
3 Correct 38 ms 11868 KB Output is correct
4 Correct 22 ms 11868 KB Output is correct
5 Correct 21 ms 11868 KB Output is correct
6 Correct 22 ms 11868 KB Output is correct
7 Correct 26 ms 11868 KB Output is correct
8 Correct 25 ms 11868 KB Output is correct
9 Correct 24 ms 11868 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11868 KB Output is correct
2 Correct 3 ms 11868 KB Output is correct
3 Correct 38 ms 11868 KB Output is correct
4 Correct 22 ms 11868 KB Output is correct
5 Correct 21 ms 11868 KB Output is correct
6 Correct 22 ms 11868 KB Output is correct
7 Correct 26 ms 11868 KB Output is correct
8 Correct 25 ms 11868 KB Output is correct
9 Correct 24 ms 11868 KB Output is correct
10 Correct 3 ms 11868 KB Output is correct
11 Correct 3 ms 11868 KB Output is correct
12 Correct 35 ms 11868 KB Output is correct
13 Correct 22 ms 11868 KB Output is correct
14 Correct 22 ms 11988 KB Output is correct
15 Correct 23 ms 12064 KB Output is correct
16 Correct 26 ms 11868 KB Output is correct
17 Correct 24 ms 11864 KB Output is correct
18 Correct 23 ms 12120 KB Output is correct
19 Execution timed out 1566 ms 12440 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11868 KB Output is correct
2 Correct 3 ms 11868 KB Output is correct
3 Correct 38 ms 11868 KB Output is correct
4 Correct 22 ms 11868 KB Output is correct
5 Correct 21 ms 11868 KB Output is correct
6 Correct 22 ms 11868 KB Output is correct
7 Correct 26 ms 11868 KB Output is correct
8 Correct 25 ms 11868 KB Output is correct
9 Correct 24 ms 11868 KB Output is correct
10 Correct 3 ms 11868 KB Output is correct
11 Correct 3 ms 11984 KB Output is correct
12 Correct 29 ms 11992 KB Output is correct
13 Correct 22 ms 11868 KB Output is correct
14 Correct 24 ms 11868 KB Output is correct
15 Correct 23 ms 11868 KB Output is correct
16 Correct 33 ms 11868 KB Output is correct
17 Correct 25 ms 11868 KB Output is correct
18 Correct 24 ms 11868 KB Output is correct
19 Execution timed out 1529 ms 18020 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1537 ms 16116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11868 KB Output is correct
2 Execution timed out 1592 ms 15900 KB Time limit exceeded
3 Halted 0 ms 0 KB -