Submission #1217672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217672		trimkus	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	2098 ms	129080 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
const int LOG = 21;
const int MAXM = 1e5;
int lift[MAXM + 1][LOG + 2];

struct RMQ {
	vector<int> tree;
	int n;
	void init(int n, int val) {
		this->n = n;
		tree = vector<int>(4 * n, val);
	}
	void update_max(int i, int l, int r, int qp, int val) {
		if (l == r) {
			tree[i] = max(tree[i], val);
			return;
		}
		int m = (l + r) / 2;
		if (qp <= m) update_max(i * 2, l, m, qp, val);
		else update_max(i * 2 + 1, m + 1, r, qp, val);
		tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
	}
	void update_max(int qp, int val) {
		update_max(1, 1, n, qp, val);
	}
	int query_max(int i, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) return -1;
		if (ql <= l && r <= qr) return tree[i];
		int m = (l + r) / 2;
		return max(query_max(i * 2, l, m, ql, qr), query_max(i * 2 + 1, m + 1, r, ql, qr));
	}
	int query_max(int ql, int qr) {
		return query_max(1, 1, n, ql, qr);
	}
};

struct RMQ_MIN {
	vector<int> tree;
	int n;
	void init(int n, int val) {
		this->n = n;
		tree = vector<int>(4 * n, val);
	}
	void update_min(int i, int l, int r, int qp, int val) {
		if (l == r) {
			tree[i] = min(tree[i], val);
			return;
		}
		int m = (l + r) / 2;
		if (qp <= m) update_min(i * 2, l, m, qp, val);
		else update_min(i * 2 + 1, m + 1, r, qp, val);
		tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
	}
	void update_min(int qp, int val) {
		update_min(1, 1, n, qp, val);
	}
	int query_min(int i, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) return n + 1;
		if (ql <= l && r <= qr) return tree[i];
		int m = (l + r) / 2;
		return min(query_min(i * 2, l, m, ql, qr), query_min(i * 2 + 1, m + 1, r, ql, qr));
	}
	int query_min(int ql, int qr) {
		return query_min(1, 1, n, ql, qr);
	}
};

struct LazySeg {
	vector<int> tree;
	vector<int> lz;
	int n;
	LazySeg(int n) {
		this->n = n;
		tree = vector<int>(4 * n, n + 1);
		lz = vector<int>(4 * n, n + 1);
	}
	void push(int i) {
		if (lz[i] != -1) {
			for (int v  : {2 * i, 2 * i + 1}) {
				if (tree[v] == -1) tree[v] = lz[i];
				if (lz[v] == -1) lz[v] = lz[i];
				tree[v] = min(tree[v], lz[i]);
				lz[v] = min(lz[v], lz[i]);
			}
			lz[i] = -1;
		}
	}
	void update(int i, int l, int r, int ql, int qr, int val) {
		if (l > qr || r < ql) return;
		if (ql <= l && r <= qr) {
			if (tree[i] == -1) tree[i] = val;
			if (lz[i] == -1) lz[i] = val;
			tree[i] = min(tree[i], val);
			lz[i] = min(lz[i], val);
			return;
		}
		push(i);
		int m = (l + r) / 2;
		update(i * 2, l, m, ql, qr, val);
		update(i * 2 + 1, m + 1, r, ql, qr, val);
		tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
	}
	void update(int ql, int qr, int val) {
		update(1, 1, n, ql, qr, val);
	}
	int query(int i, int l, int r, int qp) {
		if (l == r) {
			return tree[i];
		}
		push(i);
		int m = (l + r) / 2;
		if (qp <= m) return query(i * 2, l, m, qp);
		return query(i * 2 + 1, m + 1, r, qp);
	}
};


int main() {
	//~ ofstream cout("out.txt");
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k, m;
	cin >> n >> k >> m;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= LOG; ++j) {
			lift[i][j] = -1;
		}
	}
	vector<vector<array<int, 2>>> events(n + 1), revents(n + 1);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		if (a < b) {
			int till = min(b, a + k);
			events[a].push_back({b, till});
			events[till].push_back({-b, till});
		} else {
			a = n - a + 1;
			b = n - b + 1;
			int till = min(b, a + k);
			assert(a < till);
			assert(a > 0);
			assert(b <= n);
			revents[a].push_back({b, till});
			revents[till].push_back({-b, till});
		}
	}
	vector<RMQ> lifts(LOG + 1), nrlifts(LOG + 1);
	vector<RMQ_MIN> rlifts(LOG + 1);
	{
		multiset<pair<int, int>> mt;
		for (int j = 1; j <= n; ++j) {
			for (auto& u : events[j]) {
				if (u[0] < 0) {
					mt.erase(mt.find({-u[0], u[1]}));
				} else {
					mt.insert({u[0], u[1]});
				}
			}
			if (mt.size() > 0) {
				auto it = prev(mt.end());
				lift[j][0] = it->first;
			}
		}
		for (int i = 0; i <= LOG; ++i) {
			lifts[i].init(n, -1);
			for (int j = 1; j <= n; ++j) {
				lifts[i].update_max(j, lift[j][i]);
			}
			for (int j = 1; j <= n; ++j) {
				lift[j][i + 1] = lifts[i].query_max(j, lift[j][i]);
			}
		}
	}
	{
		for (int i = 0; i <= n; ++i) {
			for (int j = 0; j <= LOG; ++j) {
				lift[i][j] = -1;
			}
		}
		multiset<pair<int, int>> mt;
		for (int j = 1; j <= n; ++j) {
			for (auto& u : revents[j]) {
				if (u[0] < 0) {
					mt.erase(mt.find({-u[0], u[1]}));
				} else {
					mt.insert({u[0], u[1]});
				}
			}
			if (mt.size() > 0) {
				auto it = prev(mt.end());
				lift[j][0] = it->first;
			}
		}
		
		for (int i = 0; i <= LOG; ++i) {
			nrlifts[i].init(n, -1);
			for (int j = 1; j <= n; ++j) {
				nrlifts[i].update_max(j, lift[j][i]);
			}
			for (int j = 1; j <= n; ++j) {
				lift[j][i + 1] = nrlifts[i].query_max(j, lift[j][i]);
			}
		}
		for (int j = 0; j <= LOG; ++j) {
			rlifts[j].init(n, n);
			vector<int> vals;
			for (int i = 1; i <= n; ++i) {
				int val = nrlifts[j].query_max(i, i);
				vals.push_back(val);
			}
			reverse(begin(vals), end(vals));
			for (int i = 1; i <= n; ++i) {
				if (vals[i - 1] != -1) {
					vals[i - 1] = n - vals[i - 1] + 1;
				} else {
					vals[i - 1] = n + 1;
				}
				rlifts[j].update_min(i, vals[i - 1]);
			}
		}
	}
	int q;
	cin >> q;
	LazySeg lz(n);
	while (q--) {
		int a, b;
		cin >> a >> b;
		queue<array<int, 3>> q;
		vector<bool> vis(n + 1);
		vector<int> dist(n + 1, -1);
		dist[a] = 0;
		vis[a] = true;
		q.push({a, a, 0});
		while (q.size()) {
			int layer = q.size();
			while (layer--) {
				int v1 = q.front()[0];
				int v2 = q.front()[1];
				int d = q.front()[2];
				//~ cout << v << " ";
				q.pop();
				int right = max(v2, lifts[0].query_max(v1, v2));
				int left = min(v1, rlifts[0].query_min(v1, v2));
				if (v1 == left && right == v2) continue;
				//~ for (int i = left; i <= right; ++i) {
					//~ if (dist[i] == -1) {
						//~ dist[i] = d + 1;
					//~ }
				//~ }
				lz.update(left, right, d + 1);
				if (right != -1 && !vis[right]) {
					vis[right] = 1;
					q.push({v1, right, d + 1});
				}
				if (left != -1 && !vis[left]) {
					vis[left] = 1;
					q.push({left, v2, d + 1});
				}
			}
		}
		//~ for (int i = 1; i <= n; ++i) {
			//~ if (dist[i] == -1) cout << "- ";
			//~ else cout << dist[i] << " ";
		//~ }
		//~ cout << "\n";
		cout << lz.query(1, 1, n, b) << "\n";
	}
	
}

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