Submission #1270374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270374		MateiKing80	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3088 ms	53356 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 = 1e9;
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); 
	//lift[nod][nredge][bit] te duci cu 2^bit noduri mai la dreapta, timpul minim si locul in care ajungi
	//de asemenea ar fie bine sa pastram in asta si timpul de asteptare pana la urmatorul avion in nodul destinatie
	
	
	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]);
			}
		}
	}
	
	/*
	for (int i = 1; i < n - 1; i ++) {
		for (int j = 0; j < (int)vec[i].size(); j ++)
			cout << lift[i][j][0].sc << " " << lift[i][j][0].fr << " ";
		cout << '\n';
	}
	*/

	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 = 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: 0 / 36
• Subtask 6: 0 / 10