Submission #937918

#	Time	Username	Problem	Language	Result	Execution time	Memory
937918		vjudge1	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	333 ms	271652 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxN = 100000;
const int LOG = 17;

int lb[maxN+1];

void precalcLb(){
	int pw = -1;
	int curr = 1;
	for(int i = 1; i <= maxN; i++){
		if(i == curr){
			curr *= 2;
			pw++;
		}
		lb[i] = pw;
	}
}

void buildSparse(vector<vector<pair<int, int>>>& sparse, vector<pair<int, int>>& dp){
	int N = (int)dp.size();
	for(int k = 0; k < LOG; k++){
		for(int i = 0; i < N; i++){
			if(k == 0) sparse[k][i] = dp[i];
			else{
				if(i - (1 << (k-1)) < 0) sparse[k][i] = sparse[k-1][i];
				else{
					sparse[k][i].first = min(sparse[k-1][i].first, sparse[k-1][i - (1 << (k-1))].first);
					sparse[k][i].second = max(sparse[k-1][i].second, sparse[k-1][i - (1 << (k-1))].second);
				}
			}
		}
	}
}

pair<int, int> querySparse(vector<vector<pair<int, int>>>& sparse, int l, int r){
	int k = lb[r - l + 1];
	pair<int, int> p1 = sparse[k][r];
	pair<int, int> p2 = sparse[k][l + (1 << k) - 1];
	// cout << "l "<< l << " r "<< r << " " << min(p1.first, p2.first) << " " << max(p1.second, p2.second) << " k "<< k << "\n";
	return {min(p1.first, p2.first), max(p1.second, p2.second)};
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	precalcLb();

	int N, K, M; cin >> N >> K >> M;
	vector<pair<int, int>> mx(N);
	for(int i = 0; i < N; i++) mx[i] = {i, i};
	vector<tuple<int, int, int>> inv;
	for(int i = 0; i < M; i++){
		int A, B; cin >> A >> B; A--; B--;
		if(A < B){
			inv.push_back({A, min(A + K - 1, B - 1), B});
		}else{
			inv.push_back({max(A - K + 1, B + 1), A, B});
		}
	}
	sort(inv.begin(), inv.end());
	// cout << "Inv:\n";
	// for(tuple<int, int, int> t : inv){
	// 	cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << "\n";
	// }
	multiset<int> elems;
	vector<vector<int>> eras(N+1);
	int ind = 0;
	for(int i = 0; i < N; i++){
		while(ind < M && get<0>(inv[ind]) == i){
			int r = get<1>(inv[ind]);
			int val = get<2>(inv[ind]);
			elems.insert(val);
			eras[r+1].push_back(val);
			ind++;
		}
		for(int x : eras[i]) elems.erase(elems.find(x));
		if(elems.empty()) continue;
		mx[i].first = min(mx[i].first, *elems.begin());
		mx[i].second = max(mx[i].second, *elems.rbegin());
	}
	// cout << "here\n";
	// cout << "Mx:\n";
	// for(int i = 0; i < N; i++){
	// 	cout << "i "<< i << " " << mx[i].first << " " << mx[i].second << endl;
	// }
	// return 0;
	vector<vector<pair<int, int>>> dp(LOG, vector<pair<int, int>>(N));
	vector<vector<vector<pair<int, int>>>> sparse(LOG, vector<vector<pair<int, int>>> (LOG, vector<pair<int, int>>(N)));
	dp[0] = mx;
	buildSparse(sparse[0], dp[0]);
	// cout << "k "<< 0 << " dp:\n";
	// for(int i = 0; i < N; i++) cout << "i: " << i << " " << dp[0][i].first << " " << dp[0][i].second << "\n";
	for(int k = 1; k < LOG; k++){
		for(int i = 0; i < N; i++){
			dp[k][i] = querySparse(sparse[k-1], dp[k-1][i].first, dp[k-1][i].second);
		}
		// cout << "k "<< k << " dp:\n";
		// for(int i = 0; i < N; i++) cout << "i: " << i << " " << dp[k][i].first << " " << dp[k][i].second << "\n";
		// break;
		buildSparse(sparse[k], dp[k]);
	}
	// return 0;
	int Q; cin >> Q;
	while(Q--){
		int S, T; cin >> S >> T; S--; T--;
		int ans = -1;
		int curr = 0;
		pair<int, int> currInv = {S, S};
		for(int k = LOG - 1; k >= 0; k--){
			pair<int, int> p = querySparse(sparse[k], currInv.first, currInv.second);
			if(p.first <= T && p.second >= T){
				ans = curr + (1 << k);
			}else{
				curr += (1 << k);
				currInv = p;
			}
		}
		cout << ans << "\n";
	}
}

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