Submission #572741

#	Time	Username	Problem	Language	Result	Execution time	Memory
572741		benson1029	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1193 ms	328784 KiB

Main

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

int n, k, m, q;
int a, b;
vector<int> l[100005], r[100005];
priority_queue< pair<int,int> > pq;
int L[100005][20][20], R[100005][20][20];
int LOG2[100005];

pair<int,int> findRange(int l, int r, int j) {
	pair<int,int> rv;
	int LOG = LOG2[r-l+1];
	rv.first = min(L[l][j][LOG], L[r-(1<<LOG)+1][j][LOG]);
	rv.second = max(R[l][j][LOG], R[r-(1<<LOG)+1][j][LOG]);
	return rv;
}

int main() {
	ios::sync_with_stdio(false);
	for(int i=2; i<=1e5; i++) LOG2[i] = LOG2[i/2] + 1;
	cin >> n >> k >> m;
	for(int i=0; i<m; i++) {
		cin >> a >> b;
		if(a < b) {
			l[a].push_back(b);
		} else {
			r[a].push_back(b);
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j:l[i]) pq.push({j, i});
		while(!pq.empty() && pq.top().second<i-k+1) pq.pop();
		R[i][0][0] = i;
		if(!pq.empty()) {
			R[i][0][0] = max(R[i][0][0], pq.top().first);
		}
	}
	while(!pq.empty()) pq.pop();
	for(int i=n; i>=1; i--) {
		for(int j:r[i]) pq.push({-j, i});
		while(!pq.empty() && pq.top().second>i+k-1) pq.pop();
		L[i][0][0] = i;
		if(!pq.empty()) {
			L[i][0][0] = min(L[i][0][0], -pq.top().first);
		}
	}
	for(int j=0; j<=19; j++) {
		if(j>0)
		for(int i=1; i<=n; i++) {
			int LL = L[i][j-1][0];
			int RR = R[i][j-1][0];
			int LOG = LOG2[RR-LL+1];
			L[i][j][0] = min(L[LL][j-1][LOG], L[RR-(1<<LOG)+1][j-1][LOG]);
			R[i][j][0] = max(R[LL][j-1][LOG], R[RR-(1<<LOG)+1][j-1][LOG]);
		}
		for(int k=1; k<=19; k++) {
			for(int i=1; i<=n; i++) {
				if(i+(1<<k)-1 > n) break;
				L[i][j][k] = min(L[i][j][k-1], L[i+(1<<(k-1))][j][k-1]);
				R[i][j][k] = max(R[i][j][k-1], R[i+(1<<(k-1))][j][k-1]);
			}
		}
	}
	cin >> q;
	while(q--) {
		cin >> a >> b;
		int ans = 0;
		if(L[a][19][0] > b || R[a][19][0] < b) {
			cout << "-1\n";
		} else {
			int ans = 0, lo = a, hi = a;
			for(int j=19; j>=0; j--) {
				pair<int,int> range = findRange(lo, hi, j);
				if(range.first > b || range.second < b) {
					ans += (1<<j);
					lo = range.first;
					hi = range.second;
				}
			}
			cout << ans+1 << "\n";
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:68:7: warning: unused variable 'ans' [-Wunused-variable]
   68 |   int ans = 0;
      |       ^~~

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