QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#34379#2. Boatfeecle641836 993ms5644kbC++204.0kb2022-06-08 14:53:432022-06-08 14:53:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-08 14:53:44]
  • 评测
  • 测评结果:36
  • 用时:993ms
  • 内存:5644kb
  • [2022-06-08 14:53:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> poly;
const int mod=1e9+7,N=1e9;
int n,L[505],R[505],jc[505]={1},ny[505]={1},pre[505],suf[505];
poly I[2];
void upd(int &x,int y){
	x=(x+y)%mod;
}
//poly 里面存点值
int Power(int x,int y){
	int r=1;
	while(y){
		if(y&1)r=1ll*r*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}
	return r;
} 
int Get(poly t,int x){
	if(x<t.size())return t[x];
	int ret=0,n=t.size()-1;
	pre[0]=x,suf[n+1]=1;
	for(int i=1;i<=n;i++)pre[i]=1ll*pre[i-1]*(x-i+mod)%mod;
	for(int i=n;i>=0;i--)suf[i]=1ll*suf[i+1]*(x-i+mod)%mod;
	for(int i=0,fl=(n%2?mod-1:1);i<=n;i++,fl=mod-fl){
		int w=1ll*t[i]*ny[i]%mod*ny[n-i]%mod*fl%mod;
		if(i)w=1ll*w*pre[i-1]%mod;
		if(i!=n)w=1ll*w*suf[i+1]%mod;
		ret=(ret+w)%mod;
	}
	return ret;
}
void _Shift(poly &t){
	t.insert(t.begin(),Get(t,mod-1)),t.pop_back();
}
poly Dot(poly p,poly q){
	//p:sz(p)-1次
	//总共:sz(p)+sz(q)-2次
	poly ret(p.size()+q.size()-1);
	for(int i=0;i<ret.size();i++)ret[i]=1ll*Get(p,i)*Get(q,i)%mod;
	return ret;
}
poly Add(poly p,poly q){
	//p:sz(p)-1次
	//总共:sz(p)+sz(q)-2次
	poly ret(max(p.size(),q.size()));
	for(int i=0;i<ret.size();i++)ret[i]=(Get(p,i)+Get(q,i))%mod;
	return ret;
}
poly _Presum(poly p,int l,int dlt){
	//g[i]=reals[i]-s[l-1]
	poly q=p;
	for(int i=1;i<p.size();i++)q[i]=(q[i]+q[i-1])%mod;
	if(p.size()>1||p[0]!=0)q.push_back((q.back()+Get(p,p.size()))%mod);
	dlt=(dlt-Get(q,(l-1+mod)%mod)+mod)%mod;
	for(auto &i:q)i=(i+dlt)%mod;
	return q;
}
struct DP{
	struct Triple{
		int l,r;
		poly t;
	};
	vector<Triple> vec;
	void Print(){
		for(auto i:vec){
			cout<<i.l<<'~'<<i.r<<'\n';
			for(auto j:i.t)cout<<j<<' ';
			puts("");
		}
	}
	void Shift(){//变成一个新函数 g(j)=f(j-1) 
		for(auto &i:vec){
			if(i.l==0&&i.t==I[0])i.l=0;
			else i.l++;
			i.r=min(i.r+1,N),_Shift(i.t);
		}
		if(vec.back().l>vec.back().r)vec.pop_back();
		if(vec.front().l>0)vec.insert(vec.begin(),{0,0,I[0]});
	}
	void Presum(){
		vector<Triple> nw;
		int curs=0;
		for(auto i:vec){
			nw.push_back({i.l,i.r,_Presum(i.t,i.l,curs)});
			curs=Get(nw.back().t,i.r);
		}
		vec=nw;
	}
	bool isz(poly x){
		for(auto i:x)if(i)return 0;
		return 1;
	}
	void Check0(){
		reverse(vec.begin(),vec.end());
		while(vec.size()>1&&isz(vec.back().t)&&isz(vec[vec.size()-2].t))vec.pop_back(),vec.back().l=0;
		reverse(vec.begin(),vec.end());
	}
	void Redo(){
		for(auto &i:vec){
			if(i.l==i.r){
				int w=Get(i.t,i.l);
				vector<int> u;
				u.push_back(w);
				i.t=u;
			}
		}
	}
}f;
DP Dot(DP l,DP r){
	int n=l.vec.size(),m=r.vec.size();
	DP ret;
	for(int i=0,j=0;i<n&&j<m;){
		assert(l.vec[i].l==r.vec[j].l);
		int R=min(l.vec[i].r,r.vec[j].r);
		ret.vec.push_back({l.vec[i].l,R,Dot(l.vec[i].t,r.vec[j].t)});
		if(l.vec[i].r==R)i++;
		else l.vec[i].l=R+1;
		if(r.vec[j].r==R)j++;
		else r.vec[j].l=R+1;
	}
	return ret;
}
DP Add(DP l,DP r){
	int n=l.vec.size(),m=r.vec.size();
	DP ret;
	for(int i=0,j=0;i<n&&j<m;){
		assert(l.vec[i].l==r.vec[j].l);
		int R=min(l.vec[i].r,r.vec[j].r);
		ret.vec.push_back({l.vec[i].l,R,Add(l.vec[i].t,r.vec[j].t)});
		if(l.vec[i].r==R)i++;
		else l.vec[i].l=R+1;
		if(r.vec[j].r==R)j++;
		else r.vec[j].l=R+1;
	}
	return ret;
}
DP Norm(DP x,int l,int r){
	DP ret;
	int i=0;
	while(x.vec[i].l<l){
		if(x.vec[i].r<l)i++;
		else {
			x.vec[i].l=l;
			break;
		}
	}
	while(x.vec.back().r>r){
		if(x.vec.back().l>r)x.vec.pop_back();
		else {
			x.vec.back().r=r;
			break;
		}
	}
	if(l>0)ret.vec.push_back({0,l-1,I[0]});
	while(i<x.vec.size())ret.vec.push_back(x.vec[i]),i++;
	if(r<N)ret.vec.push_back({r+1,N,I[0]});
	return ret;
}
int main(){
	cin>>n,I[0].push_back(0),I[1].push_back(1);
	for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%mod,ny[i]=Power(jc[i],mod-2);
	f.vec.push_back({0,N,I[1]});
	for(int i=1;i<=n;i++){
		cin>>L[i]>>R[i];
		DP t=f;
		f.Shift();
		f=Norm(f,L[i],R[i]);
		f.Presum();
		f=Add(f,t);
		f.Check0();
		f.Redo();
	}
	cout<<(Get(f.vec.back().t,1e9)-1+mod)%mod;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 79ms
memory: 3748kb

input:

500
308810287 308810287
53564892 53564892
316377768 316377768
420249597 420249597
731165653 731165653
319087025 319087025
153776963 153776963
425464316 425464316
651047701 651047701
142502072 142502072
31632388 31632388
572337890 572337890
400220429 400220429
414382974 414382974
279400752 279400752
...

output:

553232367

result:

ok single line: '553232367'

Test #2:

score: 0
Accepted
time: 82ms
memory: 3908kb

input:

500
259419237 259419237
71604627 71604627
140848485 140848485
45258355 45258355
417882612 417882612
70908445 70908445
647789306 647789306
269825295 269825295
528839543 528839543
35956097 35956097
555387597 555387597
114446845 114446845
663753828 663753828
236039707 236039707
730686123 730686123
1874...

output:

818775560

result:

ok single line: '818775560'

Test #3:

score: 0
Accepted
time: 82ms
memory: 3956kb

input:

500
409222683 409222683
424488829 424488829
415529128 415529128
852855991 852855991
199702963 199702963
121993369 121993369
660424994 660424994
247915283 247915283
11387254 11387254
198385312 198385312
49663799 49663799
640850062 640850062
123783577 123783577
460294327 460294327
41816505 41816505
77...

output:

676116158

result:

ok single line: '676116158'

Test #4:

score: 0
Accepted
time: 78ms
memory: 3796kb

input:

500
619714633 619714633
470637076 470637076
88903555 88903555
219610285 219610285
213164397 213164397
438259138 438259138
640791314 640791314
306721667 306721667
225421135 225421135
233222391 233222391
205820722 205820722
692168797 692168797
48417870 48417870
398991106 398991106
393107546 393107546
...

output:

826747956

result:

ok single line: '826747956'

Test #5:

score: 0
Accepted
time: 82ms
memory: 3876kb

input:

500
781499655 781499655
32818153 32818153
128804256 128804256
106725036 106725036
373502067 373502067
522124816 522124816
327019589 327019589
28487843 28487843
242370575 242370575
340419621 340419621
156024191 156024191
293959833 293959833
651063779 651063779
185398156 185398156
23810548 23810548
15...

output:

796144690

result:

ok single line: '796144690'

Test #6:

score: 0
Accepted
time: 78ms
memory: 3764kb

input:

500
471686 471686
89197062 89197062
4486841 4486841
223318132 223318132
5382727 5382727
6119192 6119192
6920252 6920252
7400635 7400635
8953527 8953527
9453109 9453109
10297661 10297661
11088577 11088577
11747318 11747318
13120793 13120793
13620658 13620658
13858796 13858796
14388301 14388301
146049...

output:

287072213

result:

ok single line: '287072213'

Test #7:

score: 0
Accepted
time: 81ms
memory: 3812kb

input:

500
753345 753345
807697 807697
1544540 1544540
2467957 2467957
2620013 2620013
4381651 4381651
5343267 5343267
5650005 5650005
6291995 6291995
7239714 7239714
8727983 8727983
9137734 9137734
9167898 9167898
10039210 10039210
10042325 10042325
11550040 11550040
11642995 11642995
12967910 12967910
13...

output:

454779099

result:

ok single line: '454779099'

Test #8:

score: 0
Accepted
time: 78ms
memory: 3968kb

input:

500
2121408 2121408
2590977 2590977
2954510 2954510
3391039 3391039
3456654 3456654
3749072 3749072
4891660 4891660
5175214 5175214
25595893 25595893
8207147 8207147
8471111 8471111
8542387 8542387
8571053 8571053
9561645 9561645
9686851 9686851
9766228 9766228
10735337 10735337
11488198 11488198
11...

output:

794869016

result:

ok single line: '794869016'

Test #9:

score: 0
Accepted
time: 86ms
memory: 3804kb

input:

500
1067490 1067490
187728209 187728209
2331190 2331190
2402125 2402125
2635735 2635735
2952562 2952562
2996248 2996248
3434435 3434435
3506579 3506579
4727619 4727619
4948298 4948298
6100013 6100013
7237778 7237778
9714151 9714151
11703576 11703576
148126723 148126723
14940558 14940558
16312000 163...

output:

620087548

result:

ok single line: '620087548'

Test #10:

score: 0
Accepted
time: 82ms
memory: 3896kb

input:

500
2212852 2212852
2573958 2573958
3807064 3807064
4541303 4541303
4738320 4738320
5370702 5370702
5432558 5432558
371112074 371112074
8844474 8844474
8853776 8853776
9304445 9304445
11586488 11586488
12141143 12141143
12744747 12744747
15599671 15599671
15817906 15817906
146704510 146704510
163676...

output:

271082404

result:

ok single line: '271082404'

Test #11:

score: 0
Accepted
time: 83ms
memory: 3864kb

input:

500
524893 524893
2750062 2750062
3570891 3570891
4638547 4638547
4674487 4674487
4862482 4862482
5519675 5519675
9272918 9272918
9748535 9748535
9864262 9864262
10265009 10265009
15407366 15407366
16115070 16115070
16840848 16840848
17360063 17360063
17484830 17484830
17877302 17877302
19863611 198...

output:

822157788

result:

ok single line: '822157788'

Test #12:

score: 0
Accepted
time: 84ms
memory: 3976kb

input:

500
1540808 1540808
1937564 1937564
5283319 5283319
7804041 7804041
8433829 8433829
823139355 823139355
10494027 10494027
10546482 10546482
10621868 10621868
12153702 12153702
14415814 14415814
14426450 14426450
14804293 14804293
397985392 397985392
16988704 16988704
18836771 18836771
19696492 19696...

output:

455632768

result:

ok single line: '455632768'

Test #13:

score: 0
Accepted
time: 83ms
memory: 3900kb

input:

500
245210 245210
386280 386280
901085 901085
1260725 1260725
2429888 2429888
2654946 2654946
5006386 5006386
5371303 5371303
5813686 5813686
6154770 6154770
6350055 6350055
6508782 6508782
7456974 7456974
8140422 8140422
10003117 10003117
10268361 10268361
10642582 10642582
12660838 12660838
129157...

output:

902897517

result:

ok single line: '902897517'

Test #14:

score: 0
Accepted
time: 78ms
memory: 3768kb

input:

500
1114055 1114055
1562475 1562475
2053281 2053281
3495973 3495973
5137725 5137725
5658217 5658217
8216527 8216527
309196291 309196291
10687446 10687446
12153021 12153021
13249709 13249709
14657222 14657222
16140910 16140910
16171193 16171193
17460544 17460544
53076303 53076303
18954216 18954216
20...

output:

405249073

result:

ok single line: '405249073'

Test #15:

score: 0
Accepted
time: 83ms
memory: 3820kb

input:

500
1221260 1221260
1536448 1536448
1596219 1596219
3817144 3817144
5547038 5547038
5835095 5835095
8575834 8575834
13879314 13879314
13995687 13995687
14266986 14266986
16029893 16029893
16046286 16046286
16527064 16527064
35000863 35000863
18449319 18449319
18985127 18985127
19461392 19461392
1948...

output:

346378962

result:

ok single line: '346378962'

Test #16:

score: 0
Accepted
time: 27ms
memory: 3692kb

input:

500
158450518 158450518
398419544 398419544
15852367 15852367
147721606 147721606
189509271 189509271
12933510 12933510
38041970 38041970
268576530 268576530
752348312 752348312
158603479 158603479
515657574 515657574
277993122 277993122
158450518 158450518
8997617 8997617
841673344 841673344
117222...

output:

812086153

result:

ok single line: '812086153'

Test #17:

score: 0
Accepted
time: 29ms
memory: 3788kb

input:

500
557602055 557602055
181162629 181162629
632543712 632543712
666184058 666184058
682380195 682380195
553262662 553262662
632543712 632543712
635814815 635814815
229155517 229155517
208595757 208595757
472562424 472562424
714082069 714082069
728505635 728505635
321600780 321600780
109570005 109570...

output:

908497906

result:

ok single line: '908497906'

Test #18:

score: 0
Accepted
time: 28ms
memory: 3744kb

input:

500
98524121 98524121
114027386 114027386
126071599 126071599
190426100 190426100
3643106 3643106
98524121 98524121
818260656 818260656
177510656 177510656
149595703 149595703
114980573 114980573
163331808 163331808
98524121 98524121
114980573 114980573
659960023 659960023
7634737 7634737
662508335 ...

output:

456073831

result:

ok single line: '456073831'

Test #19:

score: 0
Accepted
time: 30ms
memory: 3640kb

input:

500
242086234 242086234
698376795 698376795
261877241 261877241
844564041 844564041
183035910 183035910
382328127 382328127
80253578 80253578
203346776 203346776
912382968 912382968
93064185 93064185
431774176 431774176
278790959 278790959
363084713 363084713
273437132 273437132
678641564 678641564
...

output:

340749954

result:

ok single line: '340749954'

Test #20:

score: 0
Accepted
time: 27ms
memory: 3692kb

input:

500
96243961 96243961
558940945 558940945
262224079 262224079
535961870 535961870
518474366 518474366
96243961 96243961
783348140 783348140
181632008 181632008
584798581 584798581
173499219 173499219
52148740 52148740
2733695 2733695
2733695 2733695
284315759 284315759
643050814 643050814
457614794 ...

output:

957883219

result:

ok single line: '957883219'

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #21:

score: 22
Accepted
time: 993ms
memory: 5472kb

input:

500
2425 2847
684 2839
462 1824
1522 4144
2140 3238
1750 4806
224 703
3351 5040
2882 2950
345 3747
794 2651
991 1127
639 2031
1118 2638
1264 2846
1537 2048
745 1969
4864 4903
3354 3752
1291 4991
448 4482
297 1945
4822 4929
2538 5080
1883 4299
828 4709
1273 4804
1927 4361
254 1956
832 1451
2791 2902
...

output:

359985632

result:

ok single line: '359985632'

Test #22:

score: -22
Time Limit Exceeded

input:

500
339 3243
558 2133
2178 4549
807 2946
1183 1973
1338 2665
87 245
1836 3299
1541 4561
2167 5058
224 4908
1163 3638
1130 1657
882 2183
1261 4670
2180 4996
606 4329
268 1036
1623 2730
1680 2268
595 1838
304 4629
911 4274
1060 2803
3012 3714
2638 3860
1108 5077
4506 4843
2137 2370
2832 3573
1367 3217...

output:


result:


Subtask #3:

score: 27
Accepted

Test #41:

score: 27
Accepted
time: 88ms
memory: 4612kb

input:

100
191358459 947004691
342443850 366915813
22574423 36448174
228846908 747282766
190110113 253913299
93029730 879223713
290883541 747723417
162887369 973643964
586349400 863191444
242642824 878391136
18343882 502405347
18658435 174450786
308510413 787915209
79222154 665119810
422422946 793255277
53...

output:

167281196

result:

ok single line: '167281196'

Test #42:

score: 0
Accepted
time: 78ms
memory: 4524kb

input:

100
383581393 816569935
148622782 696834692
514001933 750928139
133856778 549893268
514506767 925250706
217782864 954840051
903391822 953609501
29918251 32907029
470521732 690436226
499464782 741535745
787778349 959778964
430781962 497845242
269734667 660122499
580335811 745113176
756807722 87971325...

output:

281268921

result:

ok single line: '281268921'

Test #43:

score: 0
Accepted
time: 88ms
memory: 4612kb

input:

100
47376766 664313233
394991487 987813102
567510996 864092804
474261027 978587193
509899432 901924991
373485619 996550948
38985049 473280384
12721037 440510222
550510929 624405552
302186547 382317878
56742034 999054012
325629327 680836214
207364731 926875891
594450942 770071514
753663655 851754873
...

output:

720025843

result:

ok single line: '720025843'

Test #44:

score: 0
Accepted
time: 98ms
memory: 4504kb

input:

100
298419616 843564930
59305155 297269005
531834796 928938169
441735148 973559139
605818424 621425326
703322783 800904117
539057263 839739855
170044757 374288196
23611398 790255887
47685709 779877820
283057492 638606328
38833997 694366776
178486963 538594252
39641281 342815660
436787994 668729197
8...

output:

826742871

result:

ok single line: '826742871'

Test #45:

score: 0
Accepted
time: 96ms
memory: 4676kb

input:

100
555348798 709755670
168305976 212781628
228849382 744856727
56990747 168240982
787296311 984214458
169406326 917964743
158730667 910083423
12190181 112640248
110033901 995322986
300818828 374776167
233036103 963819115
142239043 570131457
299911077 935341942
584668465 699560602
45776192 885937888...

output:

413352225

result:

ok single line: '413352225'

Test #46:

score: 0
Accepted
time: 173ms
memory: 5316kb

input:

100
4286365 334929271
4981537 338808196
23557681 356699543
33398390 358101339
34707941 358658676
38324357 359183774
95038043 439124352
41048045 360430437
41768720 371264235
287907515 691529451
43996090 376960454
273337618 677267192
199544359 589099362
63243951 403838291
64933918 410238579
43243549 3...

output:

44387135

result:

ok single line: '44387135'

Test #47:

score: 0
Accepted
time: 183ms
memory: 5240kb

input:

100
20024968 371243560
330351675 712369644
23278781 380556271
318072353 701674210
27372590 389713615
27686608 391001475
34068033 394316754
36509231 394786232
322674812 705258749
41512160 397511305
51856814 404987080
319088752 704784719
49917172 401779835
50075615 403955860
48661613 398682628
5406787...

output:

7399403

result:

ok single line: '7399403'

Test #48:

score: 0
Accepted
time: 173ms
memory: 5244kb

input:

100
9198943 369659170
252989538 575101349
19510121 374889661
21431381 384205475
335874543 719411028
24658942 391583394
27093001 398757268
34206074 399439383
35200850 399963001
35890489 401635559
40759287 407411585
342408092 730051987
53733306 416593228
55894064 420964533
309940688 690955410
58876958...

output:

450095995

result:

ok single line: '450095995'

Test #49:

score: 0
Accepted
time: 174ms
memory: 5360kb

input:

100
1706537 371893895
4810220 372381936
340358769 711984953
297035471 662141002
8564434 384377677
19722778 389427013
23072979 391832621
26574110 393971158
32891774 394720943
42403951 402242215
35545896 401021085
38387143 401746251
106247438 444091749
47460907 404447518
48831160 404757697
55888803 40...

output:

888369190

result:

ok single line: '888369190'

Test #50:

score: 0
Accepted
time: 182ms
memory: 5644kb

input:

100
48265690 374587600
10490181 339498659
10924429 341652033
11618636 342565709
22882930 343352180
280917927 711718056
143525633 493359100
28422578 362842787
28596159 363155050
313132775 736801779
26957300 359984482
7994339 337785020
59713146 376376490
62418047 387721020
68395789 390187577
69857186 ...

output:

639276319

result:

ok single line: '639276319'

Test #51:

score: 0
Accepted
time: 83ms
memory: 4296kb

input:

100
1742949 162238200
5430997 752445937
5803156 568237652
11057966 45859889
16561452 908042947
18085991 769134265
18336626 358689120
18795682 348214311
29825242 263584110
31772977 437320451
39282990 600273357
52063839 996154673
431097815 778404392
57718388 619194664
64482635 429954303
75271030 97973...

output:

168347538

result:

ok single line: '168347538'

Test #52:

score: 0
Accepted
time: 63ms
memory: 4288kb

input:

100
1648626 403768768
5159779 392060583
6900671 187788672
13032456 837080381
19967029 113388787
22847858 101380347
433114523 867399222
35420256 249064179
38282907 97140752
105867108 389731175
46520756 568343575
48929133 535156352
60108363 997642539
62426861 368711541
63328425 592452830
68987112 2466...

output:

837057837

result:

ok single line: '837057837'

Test #53:

score: 0
Accepted
time: 69ms
memory: 4048kb

input:

100
53206780 701552611
13840621 218491257
330624565 998078904
98973769 911024153
22946200 30809151
30492600 792406354
40153225 599727909
40822332 879404305
194847253 389278992
549204 266820571
53526336 948296016
59300922 822988813
65491195 377325445
66391645 836628006
71305961 98254149
81107245 3736...

output:

741328081

result:

ok single line: '741328081'

Test #54:

score: 0
Accepted
time: 71ms
memory: 4280kb

input:

100
19180936 742907446
30712602 726016511
115465166 974039212
38459157 639067171
803860636 849690860
39601910 254434876
42450831 456754044
93269462 775144162
96854254 824528603
97112505 879493663
109378147 415410035
111527508 375737657
134055587 662135693
117395348 395222066
119507482 207273589
1215...

output:

823390527

result:

ok single line: '823390527'

Test #55:

score: 0
Accepted
time: 80ms
memory: 4216kb

input:

100
1886273 642680910
6943573 931446211
14880352 64904283
103201125 477902958
30417827 546416691
32912079 157983903
39616607 623034286
56184085 85949067
459091897 510735743
57911294 590682791
58719158 333216740
60276280 411143700
346689031 997780767
65168037 700249153
93651140 127966867
94115121 524...

output:

362834974

result:

ok single line: '362834974'

Test #56:

score: 0
Accepted
time: 59ms
memory: 4224kb

input:

100
77671609 272592863
77671609 716914494
27023382 928910161
677153236 902303504
552323605 758630957
27023382 490658992
227579778 675744474
232777649 654222397
138358802 199004231
27023382 569163292
278927405 686537507
27023382 961069802
111671114 624392284
109815537 111671114
114800918 552323605
30...

output:

314359176

result:

ok single line: '314359176'

Test #57:

score: 0
Accepted
time: 55ms
memory: 4240kb

input:

100
192581477 989087814
299989070 611050414
92082640 929372492
119829869 323037264
244304079 849163329
440773553 704128696
884783889 989087814
991317871 996876660
440773553 691765647
405106437 813011908
636839572 708201120
432728824 874829328
179299262 874829328
776054905 923692911
195035122 5180580...

output:

512180893

result:

ok single line: '512180893'

Test #58:

score: 0
Accepted
time: 56ms
memory: 4352kb

input:

100
41487637 487367211
275195437 421488090
710727204 796623144
188296381 205905055
76552075 781934815
172638924 713853296
356278080 587428421
487367211 903535241
172317546 968527813
361033855 871754431
196327571 598825560
125634211 459115700
145591023 180881917
215745786 487367211
135265594 68641951...

output:

396562645

result:

ok single line: '396562645'

Test #59:

score: 0
Accepted
time: 45ms
memory: 4076kb

input:

100
78320887 403473171
572032610 981242610
11978066 791716543
114129022 595561934
177474817 981242610
828535510 969726696
363454560 368689441
437807247 981242610
249869343 527417142
261430050 349760196
727425346 956667128
68733386 909478454
222021776 727046685
317576170 572032610
570121960 572072206...

output:

67963454

result:

ok single line: '67963454'

Test #60:

score: 0
Accepted
time: 71ms
memory: 4336kb

input:

100
259780149 408143598
295251037 615898303
540680082 605229613
105297737 408143598
558572348 913604801
6634559 605229613
567181468 823596652
274912464 474921194
264891697 273354761
295251037 758122576
772619047 787443235
200069291 920935697
105297737 787443235
103695458 199104344
133070258 63987630...

output:

992480862

result:

ok single line: '992480862'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%