Submission #1146990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146990		ducksaysquack	Event Hopping (BOI22_events)	C++20	0 / 100	266 ms	31760 KiB

events

#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
struct segtree {
	vector<pair<int,int>> v; vector<pair<pair<int,int>,int>> a;
	void resz(int n, vector<pair<pair<int,int>,int>> w) {v.assign(4*n,{1e18,1e18}); a = w;}
	void init(int k, int l, int r) {
		if(l > r) return; if(l == r) v[k].f = a[l].f.s, v[k].s = l+1;
		else {int m = (l+r)/2; init(2*k,l,m); init(2*k+1,m+1,r); v[k] = min(v[2*k],v[2*k+1]);}
	}
	void upd(int k, int l, int r, int p, int x) {
		if(l > r) return; if(l == r) {v[k].f = x; return;}
		int m = (r+l)/2; if(p <= m) upd(2*k,l,m,p,x); else upd(2*k+1,m+1,r,p,x);
		v[k] = min(v[2*k],v[2*k+1]);
	}
	pair<int,int> prod(int k, int x, int y, int l, int r) {
		if(l == x && y == r) return v[k]; if(l > r) return {1e18,1e18};
		int m = (x+y)/2; return min(prod(2*k,x,m,l,min(m,r)),prod(2*k+1,m+1,y,max(l,m+1),r));
	}
};
signed main() {
	int n, k; cin >> n >> k; vector<pair<pair<int,int>,int>> v(n);
	for(int i=0;i<n;i++) {cin >> v[i].f.s >> v[i].f.f; v[i].s = i+1;}
	sort(begin(v),end(v)); vector<int> w(n), z(n); for(int i=0;i<n;i++) w[i] = v[i].f.f, z[v[i].s-1] = i+1;
	int c = log2(n)+1; vector<vector<int>> t(n+1,vector<int>(c)); t[0][0] = -1, t[1][0] = -1;
	segtree r; r.resz(n,v); r.init(1,0,n-1);
	for(int i=1;i<n;i++) {
		r.upd(1,0,n-1,i,1e18);
		t[i+1][0] = r.prod(1,0,n-1,lower_bound(begin(w),end(w),v[i].f.s)-begin(w),upper_bound(begin(w),end(w),v[i].f.f)-begin(w)-1).s;
	 	r.upd(1,0,n-1,i,v[i].f.s); if(lower_bound(begin(w),end(w),v[i].f.s)-begin(w) == upper_bound(begin(w),end(w),v[i].f.f)-1-begin(w)) t[v[i].s][0] = -1;
	 	if(t[i+1][0] == 1e18) t[i+1][0] = -1;
	 	//cout << lower_bound(begin(w),end(w),v[i].f.s)-begin(w) << ' ' << upper_bound(begin(w),end(w),v[i].f.f)-begin(w)-1 << '\n';
	}
	for(int i=1;i<c;i++) for(int j=0;j<=n;j++) if(t[j][i-1] == -1) t[j][i] = -1; else t[j][i] = t[t[j][i-1]][i-1];
	while(k--) {
		int x, y, a = 0; cin >> x >> y; x--, y--; int b = z[y];
		if(x == y) {cout << "0\n"; continue;}
		for(int i=c-1;i>=0;i--) {if(t[b][i] >= z[x]) a += (1<<i), b = t[b][i]; if(b == -1) break; /*cout << a << ' ' << b << '\n';*/}
		if(b == z[x]) cout << a << '\n'; else cout << "impossible\n";
	}
	//for(auto i:t) {for(auto j:i) cout << j; cout << '\n';}
}

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