Submission #1270378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270378		MateiKing80	Escape Route 2 (JOI24_escape2)	C++20	90 / 100	3093 ms	53312 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

using pii = pair<int, int>;
#define fr first
#define sc second

pii join(pii a, pii b) {
	return {a.fr + b.fr, b.sc};
}

int B = 400;
const int inf = 1e16;

signed main() {
	int n, t;
	cin >> n >> t;
	
	vector<vector<pair<int, int>>> vec(n);
	
	for (int i = 1; i <= n - 1; i ++) {
		int m;
		cin >> m;
		for (int j = 1; j <= m; j ++) {
			int a, b;
			cin >> a >> b;
			vec[i].push_back({a, b});
		}
		sort(vec[i].begin(), vec[i].end(), [&] (pii a, pii b) {return a.sc < b.sc;});
	}
	
	vector<vector<vector<pair<int, int>>>> lift(n); 
	
	for (int i = 1; i < n - 1; i ++) {
		lift[i].resize(vec[i].size(), vector<pair<int, int>> (20));
		int p = 0;
		for (int j = 0; j < (int)vec[i].size(); j ++) {
			while (p < (int)vec[i + 1].size() && vec[i + 1][p].fr < vec[i][j].sc)
				p ++;
			if (p < (int)vec[i + 1].size())
				lift[i][j][0] = {vec[i + 1][p].fr - vec[i][j].fr, p};
			else
				lift[i][j][0] = {vec[i + 1][0].fr + t - vec[i][j].fr, 0};
		}
	}
	for (int i = 1; i < 20; i ++) {
		for (int j = 1; j < n - 1; j ++) {
			for (int k = 0; k < (int)vec[j].size(); k ++) {
				if (j + (1 << i) >= n)
					continue;
				lift[j][k][i] = join(lift[j][k][i - 1], lift[j + (1 << (i - 1))][lift[j][k][i - 1].sc][i - 1]);
			}
		}
	}
	
	auto time = [&] (int l, int k, int r) {
		pii ans = {0, k};
		for (int i = 19; i >= 0; i --) {
			if (l + (1 << i) < r) {
				ans = join(ans, lift[l][ans.sc][i]);
				l += (1 << i);
			}
		}
		return ans.fr + vec[r - 1][ans.sc].sc - vec[r - 1][ans.sc].fr;
	};

	int q;
	cin >> q;
	vector<int> ans(q, inf);
	vector<vector<pii>> addQuery(n);
	
	for (int i = 0; i < q; i ++) {
		int l, r;
		cin >> l >> r;
		if ((int)vec[l].size() >= B) {
			addQuery[l].push_back({r, i});
		} else {
			for (int j = 0; j < (int)vec[l].size(); j ++) {
				ans[i] = min(ans[i], time(l, j, r));
			}
		}
	}
	
	for (int i = 1; i < n; i ++) {
		if (addQuery[i].empty())
			continue;
		sort(addQuery[i].begin(), addQuery[i].end());
		vector<int> vp;
		int minn = inf;
		for (int j = 0; j < (int)vec[i].size(); j ++) {
			minn = min(minn, vec[i][j].sc - vec[i][j].fr);
			vp.push_back(0);
		}
		int p = 0;
		for (int j = i + 1; j <= n; j ++) {
			while (p < (int)addQuery[i].size() && addQuery[i][p].fr == j) {
				ans[addQuery[i][p].sc] = minn;
				p ++;
			}
			if (j == n || p == (int)addQuery[i].size())
				break;
			minn = inf;
			vector<int> vp2((int)vec[j].size(), inf);
			for (int k = 0; k < (int)vec[j - 1].size(); k ++)
				vp2[lift[j - 1][k][0].sc] = min(vp2[lift[j - 1][k][0].sc], vp[k] + lift[j - 1][k][0].fr);
			for (int k = 0; k < (int)vec[j].size(); k ++)
				minn = min(minn, vp2[k] + vec[j][k].sc - vec[j][k].fr);
			vp = vp2;
		}
	}

	for (int i = 0; i < q; i ++)
		cout << ans[i] << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 36 / 36
• Subtask 6: 0 / 10