oj.uz

Submission #574186

# Submission time Handle Problem Language Result Execution time Memory
574186 2022-06-08T06:55:54 Z 8e7 Event Hopping (BOI22_events) C++17
30 / 100
 185 ms 21784 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
pii seg[maxn];
vector<int> ev[maxn];
bool on[maxn];
int to[17][maxn];
int main() {
	io
	int n, q;
	cin >> n >> q;
	{
		vector<int> val;
		for (int i = 1;i <= n;i++) {
			cin >> seg[i].ff >> seg[i].ss;
			val.push_back(seg[i].ff);
			val.push_back(seg[i].ss);
		}
		sort(val.begin(), val.end());
		val.resize(int(unique(val.begin(), val.end()) - val.begin()));
		for (int i = 1;i <= n;i++) {
			seg[i].ff = lower_bound(val.begin(), val.end(), seg[i].ff) - val.begin();
			seg[i].ss = lower_bound(val.begin(), val.end(), seg[i].ss) - val.begin();
			ev[seg[i].ff].push_back(i);
			ev[seg[i].ss].push_back(i);
		}
	}
	seg[0].ss = inf;
	priority_queue<pii, vector<pii>, less<pii> > pq;
	for (int i = 0;i < 2*n;i++) {
		vector<int> tmp;
		for (int j:ev[i]) {
			if (!on[j]) {
				on[j] = 1;
				pq.push({seg[j].ss, j});
			} else {
				tmp.push_back(j);
			}
		}
		while (pq.size() && pq.top().ff <= i) pq.pop();
		for (int j:tmp) {
			to[0][j] = (pq.size() ? pq.top().ss : 0);
		}
	}
	//pary(to[0], to[0] + n + 1);
	for (int i = 1;i < 17;i++) {
		for (int j = 0;j <= n;j++) to[i][j] = to[i-1][to[i-1][j]];
	}
	while (q--) {
		int s, t;
		cin >> s >> t;	
		int ans = -1;
		if (seg[t].ss >= seg[s].ss) {
			if (seg[t].ff <= seg[s].ss) {
				if (s == t) ans = 0;
				else ans = 1;
			} else {
				int cur = s, dis = 0;
				for (int i = 16;i >= 0;i--) {
					if (seg[to[i][cur]].ss < seg[t].ff) {
						cur = to[i][cur];
						dis += 1<<i;
					}
				}
				if (to[0][cur] != 0 && seg[to[0][cur]].ss <= seg[t].ss && seg[to[0][cur]].ss >= seg[t].ff) {
					ans = dis + 2;
				} 
			}
		}
		if (ans == -1) cout << "impossible" << "\n";
		else cout << ans << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 154 ms 18076 KB Output is correct
3 Correct 135 ms 18088 KB Output is correct
4 Correct 154 ms 18112 KB Output is correct
5 Correct 158 ms 18520 KB Output is correct
6 Correct 155 ms 18732 KB Output is correct
7 Correct 135 ms 18920 KB Output is correct
8 Correct 123 ms 21784 KB Output is correct
9 Correct 129 ms 19888 KB Output is correct
10 Correct 137 ms 17632 KB Output is correct
11 Correct 151 ms 18920 KB Output is correct
12 Correct 67 ms 16820 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 18268 KB Output is correct
2 Correct 185 ms 18160 KB Output is correct
3 Correct 161 ms 18128 KB Output is correct
4 Correct 124 ms 20008 KB Output is correct
5 Correct 144 ms 17576 KB Output is correct
6 Correct 152 ms 21420 KB Output is correct
7 Correct 158 ms 21416 KB Output is correct
8 Correct 140 ms 21296 KB Output is correct
9 Correct 113 ms 20700 KB Output is correct
10 Correct 150 ms 21096 KB Output is correct
11 Correct 146 ms 20912 KB Output is correct
12 Correct 140 ms 21032 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 154 ms 18076 KB Output is correct
3 Correct 135 ms 18088 KB Output is correct
4 Correct 154 ms 18112 KB Output is correct
5 Correct 158 ms 18520 KB Output is correct
6 Correct 155 ms 18732 KB Output is correct
7 Correct 135 ms 18920 KB Output is correct
8 Correct 123 ms 21784 KB Output is correct
9 Correct 129 ms 19888 KB Output is correct
10 Correct 137 ms 17632 KB Output is correct
11 Correct 151 ms 18920 KB Output is correct
12 Correct 67 ms 16820 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Incorrect 3 ms 5204 KB Output isn't correct
18 Halted 0 ms 0 KB -