Submission #526421

#	Time	Username	Problem	Language	Result	Execution time	Memory
526421		benson1029	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1076 ms	347268 KiB

Main

#include<bits/stdc++.h>
using namespace std;

int n,k,m;
int a[200005], b[200005];
int logb2[200005];
int l[200005][20], r[200005][20];
int liftl[200005][20], liftr[200005][20];
int sliftl[20][200005][20], sliftr[20][200005][20];
int q, s, t;

int qryl(int x, int y) {
	if(x<1) x = 1;
	if(y>n) y = n;
	int logv = logb2[y-x+1];
	return min(l[x][logv], l[y-(1<<logv)+1][logv]);
}

int qryr(int x, int y) {
	if(x<1) x = 1;
	if(y>n) y = n;
	int logv = logb2[y-x+1];
	return max(r[x][logv], r[y-(1<<logv)+1][logv]);
}

int sqryl(int id, int x, int y) {
	if(x<1) x = 1;
	if(y>n) y = n;
	int logv = logb2[y-x+1];
	return min(sliftl[id][x][logv], sliftl[id][y-(1<<logv)+1][logv]);
}

int sqryr(int id, int x, int y) {
	if(x<1) x = 1;
	if(y>n) y = n;
	int logv = logb2[y-x+1];
	return max(sliftr[id][x][logv], sliftr[id][y-(1<<logv)+1][logv]);
}

int main() {
	cin >> n >> k >> m;
	for(int i=0; (1<<i)<=n; i++) {
		logb2[(1<<i)] = i;
	}
	for(int i=2; i<=n; i++) {
		if(logb2[i]==0) logb2[i] = logb2[i-1];
	}
	for(int i=1; i<=n; i++) {
		l[i][0] = i;
		r[i][0] = i;
	}
	for(int i=0; i<m; i++) {
		cin >> a[i] >> b[i];
		if(a[i] > b[i]) {
			l[a[i]][0] = min(l[a[i]][0], b[i]);
		} else {
			r[a[i]][0] = max(r[a[i]][0], b[i]);
		}
	}
	for(int j=1; j<20; j++) {
		for(int i=1; i<=n; i++) {
			if(i+(1<<(j-1)) <= n) {
				l[i][j] = min(l[i][j-1], l[i+(1<<(j-1))][j-1]);
				r[i][j] = max(r[i][j-1], r[i+(1<<(j-1))][j-1]);
			}
		}
	}
	for(int j=0; j<20; j++) {
		if(j==0) {
			for(int i=1; i<=n; i++) {
				liftl[i][0] = qryl(i, i+k-1);
				liftr[i][0] = qryr(i-k+1, i);
			}
		} else {
			for(int i=1; i<=n; i++) {
				liftl[i][j] = sqryl(j-1, liftl[i][j-1], liftr[i][j-1]); //liftl[liftl[i][j-1]][j-1];
				liftr[i][j] = sqryr(j-1, liftl[i][j-1], liftr[i][j-1]);
			}
		}
		for(int i=1; i<=n; i++) {
			sliftl[j][i][0] = liftl[i][j];
			sliftr[j][i][0] = liftr[i][j];
		}
		for(int k=1; k<20; k++) {
			for(int i=1; i<=n; i++) {
				if(i+(1<<(k-1)) <= n) {
					sliftl[j][i][k] = min(sliftl[j][i][k-1], sliftl[j][i+(1<<(k-1))][k-1]);
					sliftr[j][i][k] = max(sliftr[j][i][k-1], sliftr[j][i+(1<<(k-1))][k-1]);
				}
			}
		}
	}
	cin >> q;
	while(q--) {
		cin >> s >> t;
		int ans = 0, orig = s;
		int l = s, r = s, ll, rr;
		for(int i=19; i>=0; i--) {
			ll = sqryl(i, l, r); rr = sqryr(i, l, r);
			if(!(ll <= t && t <= rr)) {
				l = ll;
				r = rr;
				ans += (1<<i);
			}
		}
		ll = sqryl(0, l, r); rr = sqryr(0, l, r);
		if(ll<=t && t<=rr) cout << ans+1 << "\n";
		else cout << "-1\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:96:16: warning: unused variable 'orig' [-Wunused-variable]
   96 |   int ans = 0, orig = s;
      |                ^~~~

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