Submission #574244

#	Time	Username	Problem	Language	Result	Execution time	Memory
574244		8e7	Event Hopping (BOI22_events)	C++17	100 / 100	228 ms	25488 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;
bool on[maxn];

struct segment{
	int l, r, id;
	segment(){l = r = id = 0;}
	segment(int a, int b, int c){l = a, r = b, id = c;}
};
pii p[maxn];
segment seg[maxn];
int idx[maxn], ord[maxn];
int lv[maxn], rv[maxn];


struct query{
	int l, id;
	query(){l = id = 0;}
	query(int a, int c){l = a, id = c;}
};
vector<query> que[maxn];
struct BIT{
	int bit[17][maxn];
	void init(int n) {
		for (int i = 0;i < 17;i++) {
			for (int j = 0;j < maxn;j++) bit[i][j] = inf;
		}
	}
	void modify(int ind, int d, int val) {
		ind = maxn - 1 - ind;
		for (;ind < maxn;ind += ind & (-ind)) bit[d][ind] = min(bit[d][ind], val);
	}
	int query(int ind, int d) {
		ind = maxn - 1 - ind;
		int ret = inf;
		for (;ind > 0;ind -= ind &(-ind)) ret = min(ret, bit[d][ind]);
		return ret;
	}
} to;

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].l >> seg[i].r;
			val.push_back(seg[i].l);
			val.push_back(seg[i].r);
			seg[i].id = i;
		}
		sort(val.begin(), val.end());
		val.resize(int(unique(val.begin(), val.end()) - val.begin()));
		for (int i = 1;i <= n;i++) {
			seg[i].l = lower_bound(val.begin(), val.end(), seg[i].l) - val.begin();
			seg[i].r = lower_bound(val.begin(), val.end(), seg[i].r) - val.begin();
		}
		sort(seg+1, seg+n+1, [&] (segment x, segment y){return x.r == y.r ? x.l < y.l : x.r < y.r;});	
		for (int i = 1;i <= n;i++) {
			idx[i] = seg[i].id;	
			lv[i] = seg[i].l, rv[i] = seg[i].r;
			ord[seg[i].id] = i;
		}
	}

	//pary(to[0], to[0] + n + 1);
	for (int id = 0;id < q;id++) {
		int s, t;
		cin >> s >> t;	
		s = ord[s], t = ord[t];
		ans[id] = -1;
		if (seg[t].r >= seg[s].r) {
			if (seg[t].l <= seg[s].r) {
				if (s == t) ans[id] = 0;
				else ans[id] = 1;
			} else {
				que[ord[seg[t].id]].push_back(query(ord[seg[s].id], id));
			}
		}
	}
	to.init(n);
	for (int i = 1;i <= n;i++) {
		int ind = lower_bound(rv+1, rv+n+1, lv[i]) - rv;	
		//debug("new", i);
		//debug(ind);
		to.modify(i, 0, ind);	
		for (int x = 1;x < 17;x++) {
			int prv = to.bit[x-1][maxn - 1 - i];
			//debug(prv);
			to.modify(i, x, to.query(prv, x-1));
		}
		
		for (auto [l, id]:que[i]) {
			int cur = i;
			debug("query",l, id, cur);
			ans[id] = 0;
			for (int x = 16;x >= 0;x--) {
				int nxt = to.query(cur, x);
				//debug(nxt);
				if (nxt > l) {
					cur = nxt;
					ans[id] += 1<<x;
				}
			}
			if (to.query(cur, 0) <= l) {
				ans[id]++;
			} else {
				ans[id] = -1;
			}
		}
	}
	for (int i = 0;i < q;i++) {
		if (ans[i] == -1) cout << "impossible\n";
		else cout << ans[i] << "\n";
	}
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
events.cpp:116:4: note: in expansion of macro 'debug'
  116 |    debug("query",l, id, cur);
      |    ^~~~~

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