Submission #1033013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033013		aymanrs	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	204 ms	219988 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int K = 17;
const int nx = 1e5;
int spx[K][K][nx+1], spm[K][K][nx+1];
int d[nx+1];
int qux(int l, int r, int k){
	int dif = d[r-l+1];
	return max(spx[k][dif][l], spx[k][dif][r-(1<<dif)+1]);
}
int qum(int l, int r, int k){
	int dif = d[r-l+1];
	return min(spm[k][dif][l], spm[k][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][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][0][i] = L[i];
	}
	for(int v = 1;v < K;v++){
		for(int i = 1;i+(1<<v)-1 <= n;i++){
			spx[0][v][i] = max(spx[0][v-1][i], spx[0][v-1][i+(1<<v-1)]);
			spm[0][v][i] = min(spm[0][v-1][i], spm[0][v-1][i+(1<<v-1)]);
		}
	}
	for(int V = 1;V < K;V++){
		for(int i = 1;i <= n;i++){
			spx[V][0][i] = qux(spm[V-1][0][i], spx[V-1][0][i], V-1);
			spm[V][0][i] = qum(spm[V-1][0][i], spx[V-1][0][i], V-1);
		}
		for(int v = 1;v < K;v++){
			for(int i = 1;i+(1<<v)-1 <= n;i++){
				spx[V][v][i] = max(spx[V][v-1][i], spx[V][v-1][i+(1<<v-1)]);
				spm[V][v][i] = min(spm[V][v-1][i], spm[V][v-1][i+(1<<v-1)]);
			}
		}
	}
	int q;cin >> q;
	while(q--){
		int s, t;cin >> s >> t;
		int ans = 0;
		int Ls = s, Rs = s;
		for(int i = K-1;i >= 0;i--){
			if(qum(Ls, Rs, i) > t || qux(Ls, Rs, i) < t){
				ans |= 1<<i;
				int ols = Ls;
				Ls = qum(Ls, Rs, i);
				Rs = qux(ols, Rs, i);
			}
		}
		if(qum(Ls, Rs, 0) <= t && qux(Ls, Rs, 0) >= t) cout << ans+1 << '\n';
		else cout << "-1\n";
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:46:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   46 |    spx[0][v][i] = max(spx[0][v-1][i], spx[0][v-1][i+(1<<v-1)]);
      |                                                         ~^~
Main.cpp:47:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   47 |    spm[0][v][i] = min(spm[0][v-1][i], spm[0][v-1][i+(1<<v-1)]);
      |                                                         ~^~
Main.cpp:57:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   57 |     spx[V][v][i] = max(spx[V][v-1][i], spx[V][v-1][i+(1<<v-1)]);
      |                                                          ~^~
Main.cpp:58:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   58 |     spm[V][v][i] = min(spm[V][v-1][i], spm[V][v-1][i+(1<<v-1)]);
      |                                                          ~^~

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