Submission #1312093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312093		namhh	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	201 ms	58560 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
const int lg = 18;
int n,k,m,q,mn[N][lg],mx[N][lg],l[N][lg],r[N][lg],idmx[N][lg],idmn[N][lg],lim[2];
vector<pii>a[2];
void build1(int id){
	for(int i = 1; i <= lim[id]; i++) mn[i][0] = mx[i][0] = a[id][i-1].se;
	for(int j = 1; j < lg; j++){
		for(int i = 1; i+(1 << j)-1 <= lim[id]; i++){
			mn[i][j] = min(mn[i][j-1],mn[i+(1 << (j-1))][j-1]);
			mx[i][j] = max(mx[i][j-1],mx[i+(1 << (j-1))][j-1]);
		}
	}
}
int getidmx(int u, int v){
	int k = __lg(v-u+1);
	int x = idmx[u][k];
	int y = idmx[v-(1 << k)+1][k];
	if(r[x][0] <= r[y][0]) return y;
	return x;
}
int getidmn(int u, int v){
	int k = __lg(v-u+1);
	int x = idmn[u][k];
	int y = idmn[v-(1 << k)+1][k];
	if(l[x][0] <= l[y][0]) return x;
	return y;
}
void build2(){
	for(int i = 1; i <= n; i++) idmx[i][0] = idmn[i][0] = i;
	for(int j = 1; j < lg; j++){
		for(int i = 1; i+(1 << j)-1 <= n; i++){
			int x = idmx[i][j-1];
			int y = idmx[i+(1 << (j-1))][j-1];
			if(r[x][0] <= r[y][0]) idmx[i][j] = y;
			else idmx[i][j] = x;
			x = idmn[i][j-1];
			y = idmn[i+(1 << (j-1))][j-1];
			if(l[x][0] <= l[y][0]) idmn[i][j] = x;
			else idmn[i][j] = y;
		}
	}
	for(int j = 1; j < lg; j++){
		for(int i = 1; i <= n; i++){
			int x = l[i][j-1];
			int y = r[i][j-1];
			int loj1 = getidmn(x,y);
			int loj2 = getidmx(x,y);
			l[i][j] = min(l[loj1][j-1],l[loj2][j-1]);
			r[i][j] = max(r[loj1][j-1],r[loj2][j-1]);
		}
	}
}
int getmin1(int l, int r){
	int k = __lg(r-l+1);
	return min(mn[l][k],mn[r-(1 << k)+1][k]);
}
int getmax1(int l, int r){
	int k = __lg(r-l+1);
	return max(mx[l][k],mx[r-(1 << k)+1][k]);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k >> m;
	for(int i = 1; i <= m; i++){
		int u,v;
		cin >> u >> v;
		if(u < v){
			++lim[0];
			a[0].push_back({u,v});
		}
		else{
			++lim[1];
			a[1].push_back({u,v});
		}
	}
	sort(a[0].begin(),a[0].end());
	build1(0);
	for(int i = 1; i <= n; i++){
		int ll = lower_bound(a[0].begin(),a[0].end(),make_pair(i-k+1,0))-a[0].begin()+1;
		int rr = upper_bound(a[0].begin(),a[0].end(),make_pair(i+1,0))-a[0].begin();
		if(ll > rr) r[i][0] = i;
		else r[i][0] = max(i,getmax1(ll,rr));
	}
	sort(a[1].begin(),a[1].end());
	build1(1);
	for(int i = 1; i <= n; i++){
		int ll = lower_bound(a[1].begin(),a[1].end(),make_pair(i,0))-a[1].begin()+1;
		int rr = upper_bound(a[1].begin(),a[1].end(),make_pair(i+k,0))-a[1].begin();
		if(ll > rr) l[i][0] = i;
		else l[i][0] = min(i,getmin1(ll,rr));
	}
	build2();
	cin >> q;
	while(q--){
		int s,t;
		cin >> s >> t;
		int ans = 0;
		int ll = s;
		int rr = s;
		for(int i = lg-1; i >= 0; i--){
			int loj1 = getidmn(ll,rr);
			int loj2 = getidmx(ll,rr);
			int x = min(l[loj1][i],l[loj2][i]);
			int y = max(r[loj1][i],r[loj2][i]);
			if(x <= t && y >= t) continue;
			else{
				ans += (1 << i);
				ll = x;
				rr = y;
			}
		}
		int loj1 = getidmn(ll,rr);
		int loj2 = getidmx(ll,rr);
		int x = min(l[loj1][0],l[loj2][0]);
		int y = max(r[loj1][0],r[loj2][0]);
		if(x <= t && y >= t) cout << ans+1 << "\n";
		else cout << -1 << "\n";
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13