Submission #980094

#	Time	Username	Problem	Language	Result	Execution time	Memory
980094		OAleksa	Event Hopping (BOI22_events)	C++14	0 / 100	1571 ms	20692 KiB

events

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 1e5 + 69;
const int K = 18;
vector<pair<int, int>> g[2 * N];
int n, q, l[N], r[N];
int cl[N], cr[N];
int ll[N][K], rr[N][K];
//desno sa najvecom granicom i levo sa najvecom granicom
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]);
		}
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(), xs.end()), xs.end());
		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;
			g[cl[i]].push_back({0, i});
			g[cr[i]].push_back({1, i});
		}
		set<pair<int, int>> st;
		for (int i = 1;i <= 2 * n;i++) {
			sort(g[i].begin(), g[i].end());
			for (auto j : g[i]) {
				//samo sto se otvaraju
				if (j.f == 0) {	
					st.insert({cr[j.s], j.s});
				}
				else {
					rr[j.s][0] = (*st.rbegin()).s;
					st.erase({cr[j.s], j.s});
				}
			}
		}
		for (int j = 1;j < K;j++) {
			for (int i = 1;i <= n;i++) {
				rr[i][j] = rr[rr[i][j - 1]][j - 1];
			}
		}
		while (q--) {
			int x, y;
			cin >> x >> y;
			if (r[x] <= r[y]) {
				//desno
				int ans = 0, ok = 0;
				while (x != y && ans < n + 10) {
					ans += 1;
					if (r[x] > r[y]) {
						ok = 1;
						break;
					}
					x = rr[x][0];
				}
				ok |= (ans > n);
				if (!ok)
					cout << ans << '\n';
				else
					cout << "impossible\n";
			}
			else 
				cout << "impossible\n";
		}
	}
  return 0; 
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30