oj.uz

Submission #980837

# Submission time Handle Problem Language Result Execution time Memory
980837 2024-05-12T13:28:04 Z OAleksa Event Hopping (BOI22_events) C++14
0 / 100
 128 ms 25680 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 1e5 + 69;
const int K = 18;
int st[8 * N];
int n, q, l[N], r[N], pos[N];
int cl[N], cr[N];
int up[N][K];
void modify(int v, int tl, int tr, int p, int x) {
	if (tl == tr) {
		if (l[x] < l[st[v]]) 
			st[v] = x;
	}
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid)
			modify(v * 2, tl, mid, p, x);
		else
			modify(v * 2 + 1, mid + 1, tr, p, x);
		if (l[st[v * 2]] < l[st[v * 2 + 1]])
			st[v] = st[v * 2];
		else
			st[v] = st[v * 2 + 1];
	}
}
int get(int v, int tl, int tr, int x, int y) {
	if (tl > y || tr < x)
		return 0;
	else if (tl >= x && tr <= y)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		int ll = get(v * 2, tl, mid, x, y);
		int rr = get(v * 2 + 1, mid + 1, tr, x, y);	
		if (l[ll] < l[rr])
			return ll;
		return rr;
	}
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
	while (tt--) {		
		cin >> n >> q;
		vector<int> xs;
		for (int i = 1;i <= n;i++) {
			cin >> l[i] >> r[i];
			xs.push_back(l[i]);
			xs.push_back(r[i]);
		}
		l[0] = 1e9 + 10;
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		vector<pair<int, int>> ord;
		for (int i = 1;i <= n;i++) {
			cl[i] = lower_bound(xs.begin(), xs.end(), l[i]) - xs.begin() + 1;
			cr[i] = lower_bound(xs.begin(), xs.end(), r[i]) - xs.begin() + 1;
			l[i] = cl[i];
			r[i] = cr[i];
			ord.push_back({l[i], i});
		}
		sort(ord.begin(), ord.end());
		const int m = 2 * n;
		for (int j = 0;j < n;j++) {
			int i = ord[j].s;
			pos[i] = j + 1;
			int g = get(1, 1, m, l[i], r[i]);
			if (l[i] < l[g])
				up[i][0] = i;
			else
				up[i][0] = g;
			modify(1, 1, m, r[i], i);
		}
		for (int j = 1;j < K;j++) {
			for (int i = n;i >= 1;i--) {
				up[i][j] = up[up[i][j - 1]][j - 1];
			}
		}
		l[0] = 0;
		while (q--) {
			int x, y;
			cin >> x >> y;
			if (x == y) {
				cout << "0\n";
				continue;
			}
			if (r[x] <= r[y] && l[up[y][K - 1]] <= r[x]) {
				int ans = 0;
				for (int i = K - 1;i >= 0;i--) {
					if (l[up[y][i]] > r[x]) {
						ans += (1 << i);
						y = up[y][i];
					}
				}
				assert(l[y] > r[x]);
				assert(l[up[y][0]] <= r[x]);
				if (up[y][0] == x)
					ans += 1;
				else
					ans += 2;
				cout << ans << '\n';
			}
			else 
				cout << "impossible\n";
		}
	}
  return 0; 
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 102 ms 13076 KB Output is correct
3 Correct 106 ms 13100 KB Output is correct
4 Runtime error 108 ms 25680 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Runtime error 5 ms 9052 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Runtime error 5 ms 9052 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Runtime error 5 ms 9052 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 13184 KB Output is correct
2 Correct 128 ms 13128 KB Output is correct
3 Runtime error 106 ms 25528 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 102 ms 13076 KB Output is correct
3 Correct 106 ms 13100 KB Output is correct
4 Runtime error 108 ms 25680 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -