Submission #591051

#	Time	Username	Problem	Language	Result	Execution time	Memory
591051		GusterGoose27	Event Hopping (BOI22_events)	C++11	100 / 100	210 ms	26572 KiB

events

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
pii ints[MAXN];
pair<pair<int, bool>, int> endpoints[2*MAXN];
int next_int[MAXN][20];
int prev_int[MAXN][20];
int n, q;
int ints_sort[MAXN];
const int inf = 2e9;

class STree {
public:
	int n;
	int *mn_left;
	int n_orig;
	STree(int nn) {
		n_orig = nn;
		n = pow(2, ceil(log2(nn)));
		mn_left = new int[2*n];
		fill(mn_left, mn_left+2*n, 0);
		for (int i = 0; i < nn; i++) mn_left[i+n] = ints_sort[i];
		for (int i = n-1; i > 0; i--) {
			int la = ints[mn_left[2*i]].first;
			int lb = ints[mn_left[2*i+1]].first;
			if (la <= lb) mn_left[i] = mn_left[2*i];
			else mn_left[i] = mn_left[2*i+1];
		}
	}
	int get_l(int i) {
		int lval = ints[i].first;
		int rval = ints[i].second;
		int mn = -1;
		int mx = n_orig-1;
		while (mx > mn+1) {
			int cur = (mn+mx)/2;
			if (ints[ints_sort[cur]].second >= lval) mx = cur;
			else mn = cur;
		}
		int l = mx+n;
		mn = 0;
		mx = n_orig;
		while (mx > mn+1) {
			int cur = (mn+mx)/2;
			if (ints[ints_sort[cur]].second <= rval) mn = cur;
			else mx = cur;
		}
		int r = mx+n;
		int best = i;
		while (r > l) {
			if (l & 1) {
				if (ints[best].first > ints[mn_left[l]].first) best = mn_left[l];
				l++;
			}
			if (r & 1) {
				--r;
				if (ints[best].first > ints[mn_left[r]].first) best = mn_left[r];
			}
			l /= 2;
			r /= 2;
		}
		return best;
	}
};

struct comp {
	bool operator()(const int &a, const int &b) {
		return (ints[a].second == ints[b].second) ? (a < b) : (ints[a].second < ints[b].second);
	}
} comp;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		ints[i] = pii(x, y);
		endpoints[2*i] = pair<pair<int, bool>, int>(pair<int, bool>(x, 0), i);
		endpoints[2*i+1] = pair<pair<int, bool>, int>(pair<int, bool>(y, 1), i);
		ints_sort[i] = i;
	}
	sort(ints_sort, ints_sort+n, comp);
	sort(endpoints, endpoints+2*n);
	set<pii, greater<pii>> open;
	for (int i = 0; i < 2*n; i++) {
		pair<pair<int, bool>, int> ev = endpoints[i];
		if (ev.first.second == 0) open.insert(pii(ints[ev.second].second, ev.second));
		else {
			pii t = *(open.begin());
			next_int[ev.second][0] = t.second;
			open.erase(pii(ev.first.first, ev.second));
		}
	}
	STree s(n);
	for (int i = 0; i < n; i++) {
		prev_int[i][0] = s.get_l(i);
	}
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < n; j++) {
			next_int[j][i] = next_int[next_int[j][i-1]][i-1];
			prev_int[j][i] = prev_int[prev_int[j][i-1]][i-1];
		}
	}
	for (int i = 0; i < q; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		if (x == y) {
			cout << "0\n";
			continue;
		}
		if (ints[x].second > ints[y].second || ints[prev_int[y][19]].first > ints[x].second) {
			cout << "impossible\n";
			continue;
		}
		if (ints[y].first <= ints[x].second) {
			cout << "1\n";
			continue;
		}
		int jumps = 0;
		for (int j = 19; j >= 0; j--) {
			if (ints[next_int[x][j]].second < ints[y].first) {
				x = next_int[x][j];
				jumps += (1 << j);
			}
		}
		for (int j = 19; j >= 0; j--) {
			if (ints[prev_int[y][j]].first > ints[x].second) {
				y = prev_int[y][j];
				jumps += (1 << j);
			}
		}
		cout << (jumps+2) << "\n";
	}
}

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