QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#520915#8649. Escape Route 2green_gold_dog#54 334ms58788kbC++203.3kb2024-08-15 17:26:482024-08-15 17:26:49

Judging History

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

  • [2024-08-15 17:26:49]
  • 评测
  • 测评结果:54
  • 用时:334ms
  • 内存:58788kb
  • [2024-08-15 17:26:48]
  • 提交

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;
	vector<vector<vector<pair<ll, ll>>>> binup;
	LA(vector<vector<pair<ll, ll>>> a) {
		ll n = a.size();
		arr.resize(n);
		vector<vector<ll>> ends(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());
		}
		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, ends[i][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 = lower_bound(arr[nextv].begin(), arr[nextv].end(), ans.second) - arr[nextv].begin();
					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);
				}
			}
		}
	}
	ll get(ll v, ll x, ll dt) {
		ll sx = x, sv = v;;
		ll ans = INF64;
		for (auto i : arr[v]) {
			x = sx;
			v = sv;
			ll d = 0, t = i;
			for (ll i = LOG - 1; i >= 0; i--) {
				if ((x >> i) & 1) {
					x ^= 1 << i;
					ll num = lower_bound(arr[v].begin(), arr[v].end(), t) - arr[v].begin();
					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;
				}
			}
			assign_min(ans, d * dt + t - i);
		}
		return 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);
	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: 6
Accepted

Test #1:

score: 6
Accepted
time: 29ms
memory: 3896kb

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: 6
Accepted
time: 43ms
memory: 4316kb

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:

152061320763
364193581975
101659406868
515885206553
273965799122
114948644944
78108129814
549857539900
166576516139
266640269522
36194858709
249707922175
12419530470
164111155048
607789899481
370597406072
100093371327
351888389540
72528927782
102643452509
26254171517
335577444460
126061743618
214062...

result:

ok 235294 lines

Test #3:

score: 6
Accepted
time: 59ms
memory: 4764kb

input:

2000 1000000000
1
251243678 591560449
1
994358883 999558886
1
322667352 514836853
1
538977337 603533309
1
249401760 363153703
1
104249966 416969473
1
103160611 933539967
1
300026318 706474995
1
637853185 969624295
1
612852422 686323121
1
890842468 964096005
1
127364216 656085651
1
565856726 79766828...

output:

804591361552
615732551026
616673957607
255388778080
246824759617
250452018635
3920166700
411598001493
191141891280
437294118321
839203030077
237616086785
395724762439
24493946848
261496520138
440921377339
879523097721
632991245786
629587780307
208737211703
514022647807
1235201434706
1239644739996
51...

result:

ok 300000 lines

Test #4:

score: 6
Accepted
time: 46ms
memory: 4656kb

input:

2000 702597566
1
234199188 250686543
1
187177414 485066634
1
187177414 584601655
1
187177414 584601655
1
472618361 588604455
1
619085294 688959957
1
619085294 661784753
1
218487968 619085294
1
619085294 642882128
1
260718505 642882128
1
599405824 642882128
1
609069701 699150927
1
609069701 702336507...

output:

1015957000190
680210081647
1242056863771
237697116977
4956604203
134440244240
408395990203
826647972707
545108473847
444013368984
460270771687
398420505294
739873557581
11886903864
782516902871
622468211441
160076268243
501156545599
68094738139
94221928973
846316719734
79740931643
53785803546
225843...

result:

ok 235294 lines

Test #5:

score: 6
Accepted
time: 64ms
memory: 4712kb

input:

2000 1000000000
1
68118109 979507132
1
314757325 876264736
1
314757325 876264736
1
67889892 777031974
1
482602023 935398234
1
262404428 482602023
1
339427172 407785939
1
387917774 407785939
1
326338674 387917774
1
470606759 626121253
1
479458047 617726881
1
497240208 588812091
1
27983270 580400619
1...

output:

1058954050793
1702912646711
1725931854894
847704535346
735930701349
957982043978
689218108574
1014888485270
1253926159509
5082345003
326705049247
551722648510
670690834144
772997962207
64935508636
584174883094
608974709405
109201814393
118555421706
191964764942
1461647551481
1384656185989
3160951073...

result:

ok 300000 lines

Test #6:

score: 6
Accepted
time: 59ms
memory: 4804kb

input:

2000 1000000000
1
0 318307689
1
221844870 244163115
1
22662231 115199498
1
74219194 235801812
1
2902409 380433342
1
168375604 683138088
1
11701354 403914303
1
168632344 336967772
1
71867910 459961453
1
152644723 678746968
1
600952102 753759227
1
623175732 906107261
1
630957186 647533253
1
283639625 ...

output:

1501632404753
1875961436118
1998999999999
230648011712
554515884946
1810332112158
1414199310905
464373332232
756701388718
1232357794991
594169425622
207539360194
1483145438544
601736569489
71450010792
12219064269
262122526111
724970057025
409281412575
949114178961
415313478501
59936197914
1681006375...

result:

ok 300000 lines

Test #7:

score: 6
Accepted
time: 48ms
memory: 4364kb

input:

1384 702597566
1
91563503 395118179
1
272969378 336163563
1
93593482 288383752
1
641844047 657030228
1
24174550 474302755
1
483624997 516514674
1
223419444 649396752
1
277453784 660782113
1
217174776 378882844
1
315641289 693735319
1
251526833 482373541
1
381889032 694179867
1
103075862 361871540
1
...

output:

320794118590
115764966304
385279850930
10774072710
147778102717
240803564048
431539589908
290543953614
569466251816
22113396174
135588695866
228196386401
212848381901
88271083633
28719105225
481452322932
162201684606
579266864
322128177133
432606465712
97136428753
117887869786
563426915735
106522969...

result:

ok 235294 lines

Test #8:

score: 6
Accepted
time: 59ms
memory: 4768kb

input:

2000 1000000000
1
351194706 960606958
1
63449901 293827916
1
251243678 591560449
1
130608720 233558964
1
711982590 994358883
1
64238880 999558886
1
373830184 840719930
1
450224484 514836853
1
322667352 903701287
1
258721955 861235059
1
229925996 538977337
1
546018536 603533309
1
656999554 814169249
...

output:

917540572198
186307563686
364348161985
671810713222
368143529864
751354141909
398419559458
596576418307
19619304924
8364848267
507434978682
500879172382
200335632587
667972088008
955278113757
1106615668453
1200860863382
717853707983
277931060293
664485590193
152444963228
296133779011
563469393776
33...

result:

ok 300000 lines

Subtask #2:

score: 8
Accepted

Dependency #1:

100%
Accepted

Test #9:

score: 8
Accepted
time: 116ms
memory: 4416kb

input:

401 1000000000
5
220371372 336231535
896142843 932588962
50422118 103225530
657147900 709375447
431588410 552424272
5
640842473 746383340
810978611 953826580
275021460 368433859
462990882 571587967
58700188 103678512
5
671571439 779339183
471320804 598246091
2249112 160803576
865566830 948052278
222...

output:

58015892805
52459605973
79838077191
17461955998
14664444928
41031111167
44824194366
23803651939
61071315346
12828269099
37025588232
22632816685
3687297996
23869715688
53256120071
26611104179
27660022154
43657337431
43421554887
33052332827
444354092
2245599618
3207243655
52828823244
29244408625
18672...

result:

ok 300000 lines

Test #10:

score: 8
Accepted
time: 141ms
memory: 4412kb

input:

401 1000000000
5
530204134 539929589
13144227 22318244
346386878 374628522
243477806 318307686
24550570 176767937
5
318307686 346386878
539929589 592275682
176767937 243477806
22318244 24550570
374628522 530204134
5
24550570 176767937
243477806 318307686
13144227 22318244
530204134 539929589
3463868...

output:

37011406343
19273967996
39579131455
169618941
18197860585
17273967996
13296451783
27169618941
3415507745
1333242651
26169618941
23517611345
8273967996
21517611345
1009174017
12526785362
27131150716
10333242651
20230333579
14056320836
22011406343
17296451783
3131150716
18011406343
20517611345
4352310...

result:

ok 300000 lines

Test #11:

score: 8
Accepted
time: 122ms
memory: 4324kb

input:

401 1000000000
4
848784509 854990717
82539068 388749940
876647585 917845619
434252359 592889838
5
917845619 963887179
388749940 434252359
854990717 876647585
592889838 848784509
79661360 82539068
4
434252359 592889838
876647585 917845619
82539068 388749940
848784509 854990717
5
79661360 82539068
854...

output:

39069061110
33115102670
49881348111
37483593260
28483593260
20529095679
9838184259
28108896462
16575137239
27529095679
6838184259
40027863076
11108896462
30062854902
23881348111
15370997341
27069061110
11529634820
13370997341
4069061110
38115102670
28575137239
16006206208
324955781
10529095679
23115...

result:

ok 300000 lines

Test #12:

score: 8
Accepted
time: 123ms
memory: 4620kb

input:

401 1000000000
4
494963273 820408129
83880819 120938110
842771080 916665396
126044810 290806569
5
64152734 83880819
820408129 842771080
290806569 494963273
120938110 126044810
916665396 991266558
4
126044810 290806569
83880819 120938110
842771080 916665396
494963273 820408129
5
820408129 842771080
6...

output:

44795843296
23631081537
49907385739
29907385739
32283273730
2448035489
23056785376
14674555144
35056785376
3206925750
22206925750
11674555144
6448035489
13470398440
2061892076
13448035489
26061892076
674555144
1037057291
19907385739
5206925750
8631081537
2283273730
631081537
15470398440
42795843296
...

result:

ok 300000 lines

Test #13:

score: 8
Accepted
time: 76ms
memory: 4472kb

input:

601 1000000000
1
1875338 891632702
5
25665841 55060068
659511452 708955140
481273243 580847341
711209775 812323888
232189221 411128242
1
1875338 891632702
5
481273243 580847341
711209775 812323888
25665841 55060068
659511452 708955140
232189221 411128242
1
1875338 891632702
5
232189221 411128242
711...

output:

132889757364
545053184730
599053184730
349053184730
367180422927
378889757364
181053184730
214889757364
25053184730
119343850293
51180422927
165180422927
293180422927
367180422927
569343850293
449343850293
445053184730
115180422927
341053184730
218889757364
189053184730
107180422927
105343850293
272...

result:

ok 300000 lines

Test #14:

score: 8
Accepted
time: 36ms
memory: 3672kb

input:

2 1000000000
5
562116384 862271817
248809078 388152605
82837362 988267899
133736084 529736108
468265107 868556204
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...

output:

139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
139343527
...

result:

ok 300000 lines

Test #15:

score: 8
Accepted
time: 67ms
memory: 4516kb

input:

1343 1000000000
1
96816138 421462953
1
69729216 475015093
1
283255283 678004962
1
278183246 599578883
1
286424703 774388986
1
406934648 652124894
2
248195189 472085327
391961014 813907536
1
501741026 753654366
2
245060443 436672588
574556343 749900723
2
68441219 101302096
259996265 760303051
1
72484...

output:

413507395543
186533587467
765911134712
208868482018
750404829806
371009807668
207418964932
82428131468
227003029730
376762196348
758844081281
297910927314
116614837962
284886215974
115872729613
739953553340
22687331071
38063290673
8397417592
12376556003
111406561501
687952964749
12358874327
12241911...

result:

ok 300000 lines

Test #16:

score: 8
Accepted
time: 110ms
memory: 4460kb

input:

688 1000000000
3
53194187 264960020
92885755 475277088
211238915 509880505
3
6401156 232019227
469999920 577170462
554975681 644492768
2
60786527 521736047
379366223 840946783
5
419561 60298271
65502307 288235251
144008397 577008215
394990239 683091070
590837826 726885528
5
34176214 267349290
223828...

output:

68635449756
17399644966
829516162
145106947024
213624911279
172079871542
83795296584
86980633523
92389124653
242968110321
130973680158
126653516847
55386113669
195171481102
213220346364
18461195442
46294965858
108144706452
39788445054
253134167975
234247708477
234680737798
241401743091
222796922152
...

result:

ok 300000 lines

Test #17:

score: 8
Accepted
time: 73ms
memory: 4796kb

input:

1343 1000000000
1
109453710 560177810
1
661213206 913808522
1
96816138 421462953
1
193580993 240625496
1
418456250 930846898
1
69729216 475015093
2
36690281 582664217
176453344 242348112
1
283255283 678004962
2
62188679 608199380
90371766 461894091
2
278183246 599578883
255503843 861802590
1
5501148...

output:

755163082049
346535864122
512232407863
978898058885
290552425232
97892014092
196290407373
506354231170
334498014469
284757164242
115371682131
62648300672
346925420676
384891531485
477119667452
63592230021
727135372228
847646760248
640469173746
892644815785
815536555442
725960919828
92996821933
41864...

result:

ok 300000 lines

Test #18:

score: 8
Accepted
time: 86ms
memory: 4268kb

input:

688 1000000000
3
423977827 524383260
470022669 702490366
226130327 278353378
3
297592874 610688336
79889464 986165439
132108640 133164848
2
92885755 509880505
53194187 211238915
5
264960020 475277088
262659468 993117970
127768091 586472847
838692371 844797839
414832478 764033423
5
132569548 29971860...

output:

326730918498
121718776974
78578695164
28500146125
259901663572
262316540686
278578980688
83091064134
24828685743
280173281064
305172418316
69583809374
329513749863
295544205317
40964341057
32266429473
20655624467
142566212889
70252960623
218573155987
10170931375
250505042674
221374816018
41528906065...

result:

ok 300000 lines

Subtask #3:

score: 17
Accepted

Dependency #1:

100%
Accepted

Test #19:

score: 17
Accepted
time: 105ms
memory: 47108kb

input:

78947 750547470
1
163829932 170313421
1
34754818 519560348
1
93869768 456876196
1
202438570 204178463
1
98944286 525531897
1
179303298 240997860
1
134306886 372058731
1
187793519 715404428
1
126696643 473999960
1
394050514 679516860
1
286238164 460635018
1
489600305 744982147
1
157363526 311748138
1...

output:

6205466879608
20259844164215
41141586068816
37267587927279
39826818642517
4093515572405
43823341232727
17711628858751
28238993418477
40884190272133
26104208475807
13508775709102
41012054001186
35352426273830
461627182416
19671175078208
21652186528249
28225447363916
41145479364020
41071413078809
3081...

result:

ok 206901 lines

Test #20:

score: 17
Accepted
time: 164ms
memory: 58788kb

input:

100000 1000000000
1
499402020 514605324
1
766295491 995958303
1
96603365 780877499
1
712910081 985226165
1
454949900 743899539
1
21691952 722721408
1
211340490 405034439
1
85107353 123109353
1
706000294 838706369
1
38501709 366714034
1
197050586 597553366
1
394077551 422415760
1
722716322 890440304
...

output:

51002827556551
51058928322620
54456195364152
33985756298880
40843294364814
15102513736222
54474740890294
38132310544449
45962379244811
81828173456918
45953634597664
54383361960561
81724265807653
54486863608036
7943440845221
52922599405365
54528389564372
54359675413858
54480599618780
55927751535912
1...

result:

ok 300000 lines

Test #21:

score: 17
Accepted
time: 164ms
memory: 58520kb

input:

100000 1000000000
1
172079429 475324295
1
400518916 720769657
1
274370833 437066961
1
69640537 354880456
1
105708389 515119134
1
460245448 491168511
1
305736062 908867012
1
409879705 700345897
1
807448587 900734950
1
21167124 802349010
1
29646241 451672345
1
401101164 849231397
1
143742860 355220627...

output:

3322786217605
54519197542433
51507236182424
51038288475992
54515310283834
54451772579395
40445305754310
12499014691181
64287958279392
5165502765728
54536981294065
33993047573307
50203125083627
4287962267265
32543278978791
29553771479908
6634090289361
24497834416407
54510411009409
54478989372687
5448...

result:

ok 300000 lines

Test #22:

score: 17
Accepted
time: 124ms
memory: 58644kb

input:

100000 848784505
1
27033502 308637216
1
1438562 377905811
1
377905811 445448307
1
377905811 445448307
1
160564479 367847022
1
29086295 441763868
1
10492385 29086295
1
29086295 730214588
1
272693597 730214588
1
8185380 43275068
1
6374476 782898366
1
4005270 6374476
1
3501828 5751498
1
890858 5072034
...

output:

40155094458849
53957285623801
74314870396875
39710068492963
247825537284
9491774378246
1792570550982
11487043081182
39927445813086
7518209178048
1868430585731
9399975086886
42289338923347
7444371932154
16049020333361
46632817179506
40333365472902
22933944313580
38418501333554
23288694741242
47056670...

result:

ok 226053 lines

Test #23:

score: 17
Accepted
time: 147ms
memory: 58784kb

input:

100000 1000000000
1
83880822 730819402
1
35594124 752445375
1
18704793 668403352
1
17474165 931488188
1
15086956 950700936
1
35712962 969944984
1
969944984 988879345
1
978906485 997699198
1
988078833 989460959
1
333539740 989236085
1
992834981 993928865
1
993836625 993928865
1
993877892 993928865
1
...

output:

50616175045053
69001077953362
87602914201257
9400991126552
13076249428282
3302796985315
20277989521385
22218930829541
30336682428616
49125555454337
31148275992440
17955973903932
28958997325743
47631793498371
42949340374080
15065991559529
48988320931729
42577974657383
21914787769912
54987999529326
82...

result:

ok 300000 lines

Test #24:

score: 17
Accepted
time: 146ms
memory: 58656kb

input:

100000 1000000000
1
0 55060072
1
3570003 718349783
1
256078893 403790490
1
389580948 656859885
1
610267686 893795343
1
659511452 663711653
1
1875338 798640433
1
761217675 830966093
1
325102503 422332552
1
52703351 777206866
1
632813519 799618334
1
591942509 965790256
1
943567255 992355350
1
81550764...

output:

59312736241277
82196943632763
99998999999999
23986078307126
2509122248637
42012837406787
28611768219019
65210377806133
556560473013
15606679568159
5810556495394
46933725843182
71288948739119
11091807824559
90582129788769
23140905870202
17705197665416
25352553201248
38685906120426
55367891999341
9724...

result:

ok 300000 lines

Test #25:

score: 17
Accepted
time: 101ms
memory: 47048kb

input:

78947 750547470
1
12801326 300178508
1
163829932 629108909
1
170313421 475428191
1
419182442 552951314
1
34754818 519560348
1
3594075 419329694
1
456876196 654341696
1
29308134 93869768
1
83056966 497182026
1
204178463 450250065
1
202438570 465078541
1
55014422 368356153
1
98944286 386133586
1
52553...

output:

33684588782336
10599029692975
46269013081090
38276748912791
37664428117700
3243264461448
16441523547215
15541405847231
19207973709712
10394890624052
183262146076
14345085397720
28902769238369
3218092520743
33009007885846
10621151273560
29740815235729
48877373310335
36045937597311
10838456331639
2082...

result:

ok 206901 lines

Test #26:

score: 17
Accepted
time: 161ms
memory: 58692kb

input:

100000 1000000000
1
395765 716053221
1
208668935 499402020
1
514605324 573424149
1
112563488 430804151
1
766295491 995958303
1
370896512 442618404
1
155109978 225449821
1
96603365 780877499
1
305211230 986836650
1
322663385 970957503
1
712910081 985226165
1
297230409 621959309
1
208656221 743899539
...

output:

30662391785500
57766779240503
6111126043334
42002498505076
19753415630398
16369656055632
3834523157128
4728497583038
9546264570412
67330624722110
25516282773156
32679967205145
41165867776209
35357315307254
49979790494981
49838551462323
20813782279079
45227041005079
6586079790185
75982320601677
16933...

result:

ok 300000 lines

Subtask #4:

score: 23
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #27:

score: 23
Accepted
time: 327ms
memory: 44140kb

input:

20001 1000000000
5
662762967 798994894
46468971 138354131
892564074 912204331
409200282 595445952
230044234 398729067
5
57118027 151959518
229157851 303631723
814367320 981450020
659838968 768234790
439004698 573433651
5
630869543 717178196
17036982 173768392
493203667 591467829
827391797 966144141
...

output:

2668629630832
3892831280463
3999809623740
1226857097475
1113419685285
3489433065118
2368257576772
158657663807
3450834844047
68629258911
462031612601
914686104073
305462834488
526483864084
1947466042958
497468869738
948471959358
606415771236
1138412760182
1864844276046
1528229688813
710645087145
170...

result:

ok 300000 lines

Test #28:

score: 23
Accepted
time: 334ms
memory: 44004kb

input:

20001 1000000000
5
308621522 415553181
544387950 686788436
2910518 107270602
155048696 307278598
830887408 940209105
5
107270602 155048696
686788436 830887408
940209105 961624633
307278598 308621522
415553181 544387950
5
544387950 686788436
308621522 415553181
155048696 307278598
830887408 940209105...

output:

1713305711004
1320847770098
1999958714115
396260504485
443713500542
785308282579
162728764745
505713500542
928475344076
39001342924
1092412642663
228001342924
359855901028
109477734114
111477734114
716001342924
121713500542
223855901028
1287201350920
409728764745
223368412417
1371728764745
387604178...

result:

ok 300000 lines

Test #29:

score: 23
Accepted
time: 255ms
memory: 39512kb

input:

20001 1000000000
4
376385568 496774928
78267375 138949467
841454996 880233443
222277480 321404104
5
880233443 983583259
13092102 78267375
496774928 841454996
321404104 376385568
138949467 222277480
4
376385568 496774928
222277480 321404104
841454996 880233443
78267375 138949467
5
138949467 222277480...

output:

2117655319932
702209185378
2499905315884
508298118193
101905315884
1273298118193
604418507553
1189534930572
103534930572
565483682826
793209185378
1248905315884
15655319932
109142128263
1241418507553
261483682826
1705363293466
25363293466
688483682826
512534930572
1125655319932
375905315884
14730831...

result:

ok 300000 lines

Test #30:

score: 23
Accepted
time: 260ms
memory: 39488kb

input:

20001 1000000000
4
315185538 333342024
521319743 622886125
759132144 761216576
226575653 275596002
5
275596002 315185538
761216576 831323224
622886125 759132144
25143503 226575653
333342024 521319743
4
759132144 761216576
521319743 622886125
226575653 275596002
315185538 333342024
5
761216576 831323...

output:

1587294744090
1086555727222
2499604747571
300396310472
8806179721
286396310472
151057746022
26208437099
1805604747571
1865057746022
55534640923
698604747571
691534640923
1827604747571
1867396310472
816396310472
1881604747571
454736073073
1135308198521
855396310472
2172057746022
1157483536142
1031806...

result:

ok 300000 lines

Test #31:

score: 23
Accepted
time: 179ms
memory: 42144kb

input:

30001 1000000000
1
21117989 982275318
5
348955718 354892948
517766696 625348205
805456123 912649069
914857809 952207119
688887994 728026354
1
21117989 982275318
5
348955718 354892948
805456123 912649069
688887994 728026354
914857809 952207119
517766696 625348205
1
21117989 982275318
5
805456123 9126...

output:

17908961157329
20921333774959
29999333774959
25220961157329
11605067417509
12619067417509
7677333774959
1152961157329
3459333774959
3935067417509
10587440035139
28299440035139
2107440035139
23369440035139
2996961157329
8014961157329
13973067417509
13674961157329
22699333774959
3478961157329
16398961...

result:

ok 300000 lines

Test #32:

score: 23
Accepted
time: 143ms
memory: 41156kb

input:

52296 881005949
2
12638378 314608048
230277712 646023135
2
7970120 144826095
232289682 464453079
2
43074268 690542826
457137449 814350394
2
90590387 210651165
430322805 438108763
2
262122767 731114802
703888005 870307617
1
315512805 456058339
1
37476738 436885484
2
254218216 499413611
438320946 5376...

output:

15455798760730
11984607222285
20680790415602
4750544906379
3020336963331
20443131922032
23134339955552
16962146492370
9155044660439
31308651624859
20722406772139
8415826437128
14123486717595
20815714989210
20842841161072
10437622322545
17460173634323
18749758588676
18234945122566
15524384582174
1917...

result:

ok 225128 lines

Test #33:

score: 23
Accepted
time: 196ms
memory: 51868kb

input:

66656 1000000000
2
15637406 81199431
614401094 952427931
1
463757280 674231068
2
74142863 129147484
316487270 912769840
1
17077634 368244435
2
114585085 442617353
181318881 832328914
2
111870948 647897797
719462562 834163614
2
25819681 74547077
446917913 483756021
1
270282038 826567403
1
340447312 4...

output:

48099478257116
47513195224330
23132550086977
47440191378164
3259577300506
561076182783
35548782601046
47502699906957
47474804760637
25711248466185
47484643705582
761261858032
275189245596
23550672178341
45874628703220
41426247507288
10013250069301
47323222838401
40013531733954
45892625726417
4741594...

result:

ok 300000 lines

Test #34:

score: 23
Accepted
time: 234ms
memory: 31872kb

input:

22440 830108249
5
275540307 309024263
293591232 477947492
384611234 526667338
468270758 685508016
481560260 739708290
1
202061534 417627726
5
290757 18035972
38071595 99984307
162896273 445740814
189936111 476554990
195650129 497757952
2
6884658 472660927
219393347 557164578
2
169625177 613750054
36...

output:

7319209215260
6265873378031
5236894680967
5394283214691
6293940268386
3665363372040
7289438294194
7090839460098
7319712036853
3600006037646
7321019523257
7326482635715
6381021534848
8565532582826
3131065041122
3205302275744
3645505484457
355149148778
7328244396740
7291192261702
5064400938155
6860494...

result:

ok 291972 lines

Test #35:

score: 23
Accepted
time: 137ms
memory: 36624kb

input:

49512 982085869
2
191978970 744443612
363217661 667062768
1
180359100 880407268
2
259041363 304296352
284840288 673227746
1
28431521 368506138
1
565787827 607988959
2
606506192 942820159
537798608 786378991
2
15560056 480518061
289026559 655058004
2
33072594 226290400
327422566 902685917
2
796547625...

output:

2308597162767
5946652814798
12734126402298
33542731334092
22691855203909
15460214509232
67921277450
3769355551079
9269134832918
2066700010416
23221321710275
1790280231401
4885698572244
16587022444987
2319567402649
6231581337197
1569730285443
4847980348297
12252572031646
4431425874712
323080273285
32...

result:

ok 254492 lines

Test #36:

score: 23
Accepted
time: 159ms
memory: 48172kb

input:

66521 1000000000
1
100888074 724899271
1
383974339 525803786
1
177758589 746188897
2
43693161 944937876
190107805 328097669
1
368695775 645578381
1
45868643 945463129
2
35497597 487070702
280764180 520751991
1
513775132 662203314
1
675034678 810178893
1
202553257 457440383
2
215837481 534780308
2159...

output:

305388524146
45022864737159
10500954543849
8438533262456
9979743259505
10891764386746
4664517331187
22768261133015
21303458836208
9303196982744
1485429597351
9056671351860
25689271815594
21262334807113
21997538945223
4600752529138
22213030192759
27937024075201
4935426483271
13826917234397
2209475129...

result:

ok 300000 lines

Test #37:

score: 23
Accepted
time: 167ms
memory: 35620kb

input:

32773 821715347
1
164175311 554392727
4
242929741 561323824
123142278 793184407
433924283 611053664
141783625 656643810
5
188032249 555808424
117589857 174059366
292218302 339909559
595853685 796423732
258536063 409946214
3
461197698 660501754
130204943 729851049
229293561 292594636
5
113638599 3899...

output:

2403767902041
3952457478497
4219424576041
6921130818687
5804744297432
1975066807652
5505110911670
125711837119
6670873805557
13483818116043
6328129199834
7919749548120
5561471314066
7079261274207
3126792791049
4994414745336
436181846447
1036836581519
708458177153
1176489430394
4982965845456
16889214...

result:

ok 249026 lines

Test #38:

score: 23
Accepted
time: 199ms
memory: 36052kb

input:

33352 1000000000
3
459813064 681585307
340616124 676622546
11711445 912733259
3
532596838 790638350
273268662 752482101
45086207 847432666
2
559345080 933523030
255761232 569681246
5
479195731 684843831
523600630 733638311
329645549 670519127
44629253 328880643
65587746 374914231
1
351672665 7913953...

output:

597081461310
1278299205763
5674232764840
6136927831828
6722611799872
10173078126416
3640044578209
3699973517499
13775015909046
6421038243191
9778197280590
486339347256
2944327716762
521745440907
12586096772142
706809254977
2187258064338
6476947559854
3812230269532
7848120751445
11975611559905
438799...

result:

ok 300000 lines

Subtask #5:

score: 0
Time Limit Exceeded

Test #39:

score: 0
Time Limit Exceeded

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:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

0%