Submission #1128343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128343		mickey080929	Escape Route 2 (JOI24_escape2)	C++20	100 / 100	977 ms	96896 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll inf = 2e18;
const ll B = 100;

ll ri[100010][20], rt[100010][20];
ll li[100010], lt[100010];
ll pre1[100010], pre2[1010][100010];

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	ll N, T;
	cin >> N >> T;
	vector<vector<pair<ll,ll>>> a(N-1);
	vector<ll> st(N);
	ll tot = 0;
	for (ll i=0; i<N-1; i++) {
		ll M;
		cin >> M;
		a[i].resize(M);
		for (ll j=0; j<M; j++) {
			cin >> a[i][j].first >> a[i][j].second;
		}
		sort(a[i].begin(), a[i].end(), [&] (pair<ll,ll> &u, pair<ll,ll> &v) {
			return u.first != v.first ? u.first > v.first : u.second < v.second;
		});
		vector<pair<ll,ll>> t = {a[i][0]};
		for (ll j=1; j<M; j++) {
			if (a[i][j].second < t.back().second) {
				t.push_back(a[i][j]);
			}
		}
		a[i] = t;
		reverse(a[i].begin(), a[i].end());
		st[i] = tot;
		tot += a[i].size();
	}
	st[N-1] = tot;
	memset(ri, -1, sizeof(ri));
	memset(li, -1, sizeof(li));
	for (ll i=0; i<N-1; i++) {
		for (ll j=0; j<a[i].size(); j++) {
			if (i != N-2) {
				ll nxt = lower_bound(a[i+1].begin(), a[i+1].end(), make_pair(a[i][j].second, 0LL)) - a[i+1].begin();
				if (nxt == a[i+1].size()) {
					nxt = 0;
				}
				ri[st[i]+j][0] = st[i+1] + nxt;
				rt[st[i]+j][0] = (a[i+1][nxt].first - a[i][j].second + T) % T + (a[i+1][nxt].second - a[i+1][nxt].first);
			}
			if (i != 0) {
				ll prv = upper_bound(a[i-1].begin(), a[i-1].end(), make_pair(inf, a[i][j].first), 
					[&](pair<ll,ll>u, pair<ll,ll>v) {
						return u.second != v.second ? u.second < v.second : u.first < v.first;
					}) - a[i-1].begin() - 1;
				if (prv == -1) {
					prv = a[i-1].size() - 1;
				}
				li[st[i]+j] = st[i-1] + prv;
				lt[st[i]+j] = (a[i][j].first - a[i-1][prv].second + T) % T + (a[i-1][prv].second - a[i-1][prv].first);
			}
		}
	}
	for (ll lv=1; lv<=16; lv++) {
		for (ll i=0; i<tot; i++) {
			if (ri[i][lv-1] != -1 && ri[ri[i][lv-1]][lv-1] != -1) {
				ri[i][lv] = ri[ri[i][lv-1]][lv-1];
				rt[i][lv] = rt[i][lv-1] + rt[ri[i][lv-1]][lv-1];
			}
		}
	}
	vector<ll> big, sid(N-1);
	for (ll i=0; i<N-1; i++) {
		if (a[i].size() > B) {
			sid[i] = big.size();
			big.push_back(i);
		}
	}
	//assert(big.size() < 350);
	for (ll i=0; i<big.size(); i++) {
		pre2[i][big[i]] = inf;
		for (ll k=0; k<a[big[i]].size(); k++) {
			pre1[st[big[i]]+k] = 0;
			pre2[i][big[i]] = min(pre2[i][big[i]], a[big[i]][k].second - a[big[i]][k].first);
		}
		for (ll j=big[i]+1; j<N-1; j++) {
			pre2[i][j] = inf;
			for (ll k=0; k<a[j].size(); k++) {
				pre1[st[j]+k] = pre1[li[st[j]+k]] + lt[st[j]+k];
				pre2[i][j] = min(pre2[i][j], pre1[st[j]+k] + a[j][k].second - a[j][k].first);
			}
		}
	}
	ll Q;
	cin >> Q;
	while (Q --) {
		ll L, R;
		cin >> L >> R;
		L --; R -= 2;
		if (a[L].size() > B) {
			cout << pre2[sid[L]][R] << '\n';
		}
		else {
			ll ans = inf;
			for (ll i=0; i<a[L].size(); i++) {
				ll r = st[L] + i;
				ll rp = L;
				ll cur = a[L][i].second - a[L][i].first;
				for (ll lv=16; lv>=0; lv--) {
					if (rp + (1<<lv) <= R) {
						rp += 1 << lv;
						cur += rt[r][lv];
						r = ri[r][lv];
					}
				}
				ans = min(ans, cur);
			}
			cout << ans << '\n';
		}
	}
}

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