Submission #574190

#	Time	Username	Problem	Language	Result	Execution time	Memory
574190		8e7	Event Hopping (BOI22_events)	C++17	30 / 100	202 ms	28316 KiB

events

//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];

struct query{
	int l, r, id;
	query(){l = r = id = 0;}
	query(int a, int b, int c){l = a, r = b, id = c;}
};
vector<query> que[maxn];
struct BIT{
	int bit[maxn];
	void modify(int ind, int val) {
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	int query(int ind) {
		int ret = 0;
		for (;ind > 0;ind -= ind &(-ind)) ret += bit[ind];
		return ret;
	}
} bit;

int ans[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);
				on[j] = 0;
			}
		}
		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]];
	}
	for (int id = 0;id < q;id++) {
		int s, t;
		cin >> s >> t;	
		ans[id] = -1;
		if (seg[t].ss >= seg[s].ss) {
			if (seg[t].ff <= seg[s].ss) {
				if (s == t) ans[id] = 0;
				else ans[id] = 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;
					}
				}
				ans[id] = dis;
				que[seg[cur].ss].push_back(query(seg[t].ff, seg[t].ss, id));
			}
		}
	}
	for (int i = 0;i < 2*n;i++) {
		for (int j:ev[i]) {
			if (!on[j]) {
				on[j] = 1;
				bit.modify(seg[j].ss, 1);
			}
		}
		for (auto [l, r, id]:que[i]) {
			if (bit.query(r) - bit.query(l-1) > 0) ans[id] += 2;
			else ans[id] = -1;
		}
	}
	for (int i = 0;i < q;i++) {
		if (ans[i] == -1) cout << "impossible\n";
		else cout << ans[i] << "\n";
	}
}

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