Submission #1032901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032901		aymanrs	Railway Trip 2 (JOI22_ho_t4)	C++17	52 / 100	2078 ms	35768 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int K = 17;
const int nx = 1e5;
int spx[K][nx+1], spm[K][nx+1];
int d[nx+1];
int qux(int l, int r){
	int dif = d[r-l+1];
	return max(spx[dif][l], spx[dif][r-(1<<dif)+1]);
}
int qum(int l, int r){
	int dif = d[r-l+1];
	return min(spm[dif][l], spm[dif][r-(1<<dif)+1]);
}
void solve(){
	int n, k, m;cin >> n >> k >> m;
	d[1]=0;
	for(int i = 2;i <= nx;i++){
		d[i]=d[i-1];
		if(i==(i&-i)) d[i]++;
	}
	int lr[n+1] = {0}, rl[n+1];
	int L[n+1], R[n+1];
	fill(rl, rl+n+1, n+1);
	while(m--){
		int a, b;cin >> a >> b;
		if(a < b) lr[a] = max(lr[a], b);
		else rl[a] = min(rl[a], b);
	}
	multiset<int> ms;
	int ranc[K][n], lanc[K][n];
	for(int i = 1;i <= n;i++){
		ms.insert(lr[i]);
		if(i>k) ms.erase(ms.find(lr[i-k]));
		R[i] = max(*ms.rbegin(), i);
		spx[0][i]=R[i];
		ranc[0][i] = R[i];
	}

	ms.clear();
	for(int i = n;i;i--){
		ms.insert(rl[i]);
		if(i+k<=n) ms.erase(ms.find(rl[i+k]));
		L[i] = min(*ms.begin(), i);
		spm[0][i]=L[i];
		lanc[0][i]=L[i];
		for(int j = 1;j < K;j++) ranc[j][i] = ranc[j-1][ranc[j-1][i]];
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j < K;j++) lanc[j][i] = lanc[j-1][lanc[j-1][i]];
	}
	for(int v = 1;v < K;v++){
		for(int i = 1;i+(1<<v)-1 <= n;i++){
			spx[v][i] = max(spx[v-1][i], spx[v-1][i+(1<<v-1)]);
			spm[v][i] = min(spm[v-1][i], spm[v-1][i+(1<<v-1)]);
		}
	}
	int q;cin >> q;
	while(q--){
		int s, t;cin >> s >> t;
		int ans = 0;
		if(k==n-1){
			if(s<t){
				for(int i = K-1;i >= 0;i--){
					if(ranc[i][s] < t) {
						ans+=1<<i;
						s = ranc[i][s];
					}
				}
				if(ranc[0][s] >= t) cout << ans+1 << '\n';
				else cout << "-1\n";
			} else {
				for(int i = K-1;i >= 0;i--){
					if(lanc[i][s] > t) {
						ans+=1<<i;
						s = lanc[i][s];
					}
				}
				if(lanc[0][s] <= t) cout << ans+1 << '\n';
				else cout << "-1\n";
			}
		} else {
			int Ls = s, Rs = s, ans = 0;
			while(true){
				if(Ls <= t && t <= Rs){
					cout << ans << '\n';
					break;
				}
				ans++;
				int ls = qum(Ls, Rs), rs = qux(Ls, Rs);
				if(ls == Ls && rs == Rs) {
					cout << "-1\n";
					break;
				}
				Ls = ls;Rs = rs;
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:54:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   54 |    spx[v][i] = max(spx[v-1][i], spx[v-1][i+(1<<v-1)]);
      |                                                ~^~
Main.cpp:55:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   55 |    spm[v][i] = min(spm[v-1][i], spm[v-1][i+(1<<v-1)]);
      |                                                ~^~

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