QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#520947#8649. Escape Route 2green_gold_dog#0 622ms48312kbC++204.3kb2024-08-15 18:00:162024-08-15 18:00:16

Judging History

你现在查看的是最新测评结果

  • [2024-08-15 18:00:16]
  • 评测
  • 测评结果:0
  • 用时:622ms
  • 内存:48312kb
  • [2024-08-15 18:00:16]
  • 提交

answer

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007, LOG = 17;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
bool assign_min(T& a, T b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
T square(T a) {
	return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
	ll operator() (pair<ll, ll> p) const {
		return ((__int128)p.first * MOD + p.second) % INF64;
	}
};

struct LA {
	vector<vector<ll>> arr, ends, lbnxt;
	vector<vector<vector<ll>>> smk;
	vector<vector<vector<pair<ll, ll>>>> binup;
	map<pair<ll, ll>, ll> mind;
	LA(vector<vector<pair<ll, ll>>> a, ll dt) {
		ll n = a.size();
		arr.resize(n);
		ends.resize(n);
		for (ll i = 0; i < n; i++) {
			sort(a[i].begin(), a[i].end());
			ll bto = INF32;
			while (!a[i].empty()) {
				if (a[i].back().second < bto) {
					bto = a[i].back().second;
					arr[i].push_back(a[i].back().first);
					ends[i].push_back(a[i].back().second);
				}
				a[i].pop_back();
			}
			reverse(arr[i].begin(), arr[i].end());
			reverse(ends[i].begin(), ends[i].end());
		}
		lbnxt.resize(n);
		for (ll i = 1; i < n; i++) {
			lbnxt[i].resize(ends[i - 1].size());
			for (ll j = 0; j < ends[i - 1].size(); j++) {
				lbnxt[i][j] = lower_bound(arr[i].begin(), arr[i].end(), ends[i - 1][j]) - arr[i].begin();
			}
		}
		binup.resize(n);
		for (ll i = n - 1; i >= 0; i--) {
			binup[i].resize(arr[i].size());
			for (ll j = 0; j < arr[i].size(); j++) {
				binup[i][j].resize(LOG);
				binup[i][j][0] = make_pair(0, j);
				for (ll k = 1; k < LOG; k++) {
					pair<ll, ll> ans = binup[i][j][k - 1];
					ll nextv = i + (1 << (k - 1));
					if (nextv >= n) {
						break;
					}
					ll num = lbnxt[nextv][ans.second];
					if (num == arr[nextv].size()) {
						num = 0;
						ans.first++;
						ans.second = 0;
					}
					binup[i][j][k] = make_pair(ans.first + binup[nextv][num][k - 1].first, binup[nextv][num][k - 1].second);
				}
			}
		}
		smk.resize(n);
		for (ll i = 0; i < n; i++) {
			vector<ll> all;
			for (ll j = 0; j < arr[i].size(); j++) {
				all.push_back(j);
			}
			for (ll sz = 0; sz < LOG; sz++) {
				if (i + (1 << sz) > n) {
					break;
				}
				smk[i].push_back(vector<ll>(0, 0));
				ll lst = INF64;
				while (!all.empty()) {
					ll x = get(i, 1 << sz, all.back(), dt);
					if (x != lst) {
						smk[i].back().push_back(all.back());
						lst = x;
					}
					all.pop_back();
				}
				reverse(smk[i].back().begin(), smk[i].back().end());
				all = smk[i].back();
			}
		}
	}
	ll get(ll v, ll x, ll st, ll dt) {
		ll d = 0, t = st;
		bool b = true;
		for (ll i = LOG - 1; i >= 0; i--) {
			if ((x >> i) & 1) {
				x ^= 1 << i;
				ll num;
				if (b) {
					num = t;
				} else {
					num = lbnxt[v][t];
				}
				if (num == arr[v].size()) {
					num = 0;
					d++;
					t = 0;
				}
				d += binup[v][num][i].first;
				t = binup[v][num][i].second;
				v += 1 << i;
			}
		}
		return dt * d + ends[v - 1][t];
	}
	ll get(ll v, ll x, ll dt) {
		if (mind.find(make_pair(v, x)) != mind.end()) {
			return mind[make_pair(v, x)];
		}
		ll p2 = 0;
		ll nx = x;
		while (nx > 1) {
			nx /= 2;
			p2++;
		}
		ll ans = INF64;
		for (auto i : smk[v][p2]) {
			assign_min(ans, get(v, x, i, dt) - arr[v][i]);
		}
		return mind[make_pair(v, x)] = ans;
	}
};

void solve() {
	ll n, t;
	cin >> n >> t;
	vector<vector<pair<ll, ll>>> to(n - 1);
	for (ll i = 0; i < n - 1; i++) {
		ll col;
		cin >> col;
		for (ll j = 0; j < col; j++) {
			ll a, b;
			cin >> a >> b;
			to[i].emplace_back(a, b);
		}
	}
	LA la(to, t);
	ll q;
	cin >> q;
	for (ll i = 0; i < q; i++) {
		ll l, r;
		cin >> l >> r;
		l--;
		cout << la.get(l, r - l - 1, t) << '\n';
	}
}

int main() {
	if (IS_FILE) {
		freopen("", "r", stdin);
		freopen("", "w", stdout);
	}
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
	ll t = 1;
	if (IS_TEST_CASES) {
		cin >> t;
	}
	for (ll i = 0; i < t; i++) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 30ms
memory: 3864kb

input:

2 1000000000
1
359893566 955414858
300000
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 ...

output:

595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
595521292
...

result:

ok 300000 lines

Test #2:

score: 0
Wrong Answer
time: 150ms
memory: 18456kb

input:

1384 702597566
1
93593482 288383752
1
483624997 516514674
1
217174776 378882844
1
381889032 694179867
1
143192510 343368096
1
20552425 654877612
1
34995000 223673833
1
86047336 507288111
1
58193455 564074888
1
543118270 579455813
1
42236607 257802041
1
244371899 634806939
1
173261583 634917538
1
245...

output:

150656125631
362085789277
100254211736
511669621157
270452811292
113543449812
76000337116
547749747202
165171321007
264532476824
34087066011
246897531911
11716932904
162705959916
605682106783
369192210940
97282981063
349077999276
71123732650
101238257377
24146378819
332064456630
123251353354
2105490...

result:

wrong answer 1st lines differ - expected: '152061320763', found: '150656125631'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Wrong Answer

Test #39:

score: 0
Wrong Answer
time: 622ms
memory: 48312kb

input:

301 1000000000
300
863578477 865166395
261293731 262628986
290161866 292035987
31029640 32135494
288138979 289416854
321254857 322352244
163393949 166291828
897880953 899050317
840019366 842900569
100947276 102350870
520716771 522094941
820182602 822928836
766708508 769688128
727827782 728874133
740...

output:

986847074
210015534
986847074
340291594
376752401
646919150
23398481
76778858
373373643
540095714
113469318
60164999
223458267
426858638
50052816
636734034
220083324
436837938
140224434
36789711
10186037
646784751
83430230
436766837
600181308
293480714
590091050
600200671
450040181
270193472
1034634...

result:

wrong answer 1st lines differ - expected: '996840913', found: '986847074'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%