Submission #1032886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032886		aymanrs	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2068 ms	22108 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;
	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];
	}

	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];
	}
	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 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:47:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   47 |    spx[v][i] = max(spx[v-1][i], spx[v-1][i+(1<<v-1)]);
      |                                                ~^~
Main.cpp:48:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   48 |    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: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13