QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#520954#8649. Escape Route 2green_gold_dog#0 533ms28468kbC++204.4kb2024-08-15 18:10:102024-08-15 18:10:11

Judging History

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

  • [2024-08-15 18:10:11]
  • 评测
  • 测评结果:0
  • 用时:533ms
  • 内存:28468kb
  • [2024-08-15 18:10:10]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")

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

constexpr long long INF64 = 9'000'000'000'000'000'000;
constexpr ll 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));
				long long lst = INF64;
				while (!all.empty()) {
					long long 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();
			}
		}
	}
	long long 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) {
					b = false;
					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 * (long long)d + ends[v - 1][t];
	}
	long long 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++;
		}
		long long 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: 29ms
memory: 3908kb

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: 168ms
memory: 18216kb

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:

1737465403
-878638185
-1419808236
489131033
-912107822
-1015472048
798718486
101726012
-927208405
352297170
1835120341
599819007
-465371418
902397800
-2095456551
1230218616
1309123519
-298928732
-485516250
-435762595
484367741
569995372
1507692034
-686309986
-763966629
31350422
-900800492
1705037545...

result:

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

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: 36
Accepted
time: 509ms
memory: 28452kb

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:

996840913
213467673
996840913
350088722
393643222
660161043
23398481
83378757
386772057
550058707
116797789
66795163
230046137
430022213
50052816
646976316
223372288
443414533
153481147
43516132
10186037
656745708
93473524
443593864
613442576
306857640
606706973
613462088
456791451
276831487
1034634...

result:

ok 90000 lines

Test #40:

score: 36
Accepted
time: 498ms
memory: 28236kb

input:

301 1000000000
300
300066064 302323286
473632893 475766284
351370863 352221960
914819860 916333465
317977421 319127906
920520037 923283324
504830796 505586396
494369607 495452979
558040391 558539388
23365739 25905186
564630891 565459633
277441881 279789082
961207919 962159794
693338597 695347090
578...

output:

286865169
313364540
996793841
720065430
783551270
320062652
50110451
340091416
456818265
106730063
250074295
56771021
100124212
90126317
70034915
413435450
426731145
213397678
46770743
113477622
30125146
266748001
793374963
343416973
130072106
880090066
26828815
196784156
596947893
460085415
6752386...

result:

ok 90000 lines

Test #41:

score: 36
Accepted
time: 533ms
memory: 28248kb

input:

301 1000000000
300
436133849 439766906
399299656 399871397
987510123 987623863
87382570 87807552
948515445 949052052
596367083 597547004
838965514 843316163
505192505 507242632
813023000 816438712
680226676 681650508
241702689 242610357
903574024 904180573
293115387 293225805
965934333 967856315
359...

output:

375138342
196630758
480427492
72200479
226103302
192548720
405758667
18014460
276454760
287183968
7303408
148051928
324101075
70716872
167805126
79418501
87154832
328873671
90156751
401532551
18997429
2458843
110069678
86903655
870988
34835290
196364999
201922538
108740749
235174223
181778722
869036...

result:

ok 90000 lines

Test #42:

score: 36
Accepted
time: 498ms
memory: 28468kb

input:

301 1000000000
299
770778382 771390993
731130505 734282136
900324353 900756667
315720590 315879945
549885731 551694156
961870218 967237404
449686711 450724459
169164766 176907126
418234610 418840696
874086997 874800159
746489809 746815743
704004512 705083659
779639958 782291940
538072804 539490105
9...

output:

278151674
48664023
474375584
192834
89456431
315809268
464386665
92387184
365717998
311285027
11591638
42204183
161647182
166728915
160331861
116815686
458008311
11591638
185637145
210866239
134761268
3137894
49495155
157947203
6416710
216770354
112128268
54180198
20566729
15835368
202054033
4204761...

result:

ok 90000 lines

Test #43:

score: 36
Accepted
time: 518ms
memory: 28380kb

input:

301 1000000000
299
333948864 338012623
912826899 913391055
571148299 577968736
372988318 373399550
162424522 165729804
754997109 756545766
55958658 57190515
677609768 681027389
834938974 837016269
366716733 367166710
176358492 176855515
146676373 152623195
967011409 969970853
302962786 308603483
421...

output:

215116970
309596332
449007971
86708426
89020740
1378772
164417408
123121994
258650249
31734252
208339511
329295444
226562183
56266419
265427201
26290202
182058675
11508341
18364019
216120098
16779760
224579848
3856163
40562766
124790659
266181589
141282804
20226095
347296033
264493325
34033836
32337...

result:

ok 90000 lines

Test #44:

score: 0
Wrong Answer
time: 88ms
memory: 16592kb

input:

301 1000000000
300
614330645 904777865
21671200 972465607
844511005 869900059
222039406 973766970
50412921 890784128
448643606 930527499
321278854 633891369
339898318 978093316
494050725 535513007
681208047 744770267
86200056 932879083
882937423 926179572
142953625 486908718
433164812 480712775
5911...

output:

1757912356
-1084053116
81784704
98905
1724299428
-1337638238
122184230
-1255627328
-1304698362
-2018956921
2036265557
1794349578
117294019
300284111
695776684
-913553448
-239486383
-704778319
2130555618
-104600127
-569649259
1832980867
160647082
438592292
-1712090337
4586484
985006134
71394762
-1640...

result:

wrong answer 1st lines differ - expected: '10347846948', found: '1757912356'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%