QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96542#360. Cultivationtricyzhkx100 ✓1686ms5396kbC++142.6kb2023-04-14 11:04:062023-04-14 11:04:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-14 11:04:07]
  • 评测
  • 测评结果：100
  • 用时：1686ms
  • 内存：5396kb
查看
  • [2023-04-14 11:04:06]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
void chkmax(int &a,int b){a=max(a,b);}
void chkmin(int &a,int b){a=min(a,b);}
struct Point
{
	int x,y;
	bool operator<(const Point &a)const{return x<a.x;}
}a[310];
int H,W,n,p[610],L[310],R[310],pre[610],mny[610],mxy[610],mxd[610],len[200010],miny[310][310],maxy[310][310],maxd[310][310];
ll ans=1e18;
multiset<int> st;
template<class cmp>
struct Que
{
	cmp _cmp;
	int le,ri;
	pii que[610];
	void clear(){le=ri=0;}
	void push(pii x)
	{
		while(le<ri && _cmp(que[ri-1],x)) ri--;
		que[ri++]=x;
	}
	void pop(int x){while(le<ri && que[le].second<x) le++;}
	bool empty(){return le>=ri;}
	int top(){return que[le].first;}
};
Que<less<pii>> Q1,Q3;
Que<greater<pii>> Q2;
void solve(int len)
{
	int t1=0,t2=0;
	for(int i=1;i<=n;i++) L[i]=a[i].x,R[i]=L[i]+len;
	for(int i=1;i<=n;i++) p[++t1]=L[i];
	t2=t1;
	for(int i=1;i<=n;i++) p[++t2]=R[i];
	inplace_merge(p+1,p+t1+1,p+t2+1);
	t2=unique(p+1,p+t2+1)-p-1;
	for(int i=1,j=1,k=1;i<=n;i++)
	{
		for(;p[j]<L[i];j++);
		for(;p[k]<R[i];k++);
		L[i]=j;R[i]=k;
	}
	for(int i=1,j=1,k=0;i<=t2;i++)
	{
		for(;j<=n && R[j]<=i;j++);
		for(;k<n && L[k+1]<=i;k++);
		pre[i]=pre[i-1];
		if(j>k){pre[i]++;continue;}
		mny[i]=miny[j][k];mxy[i]=maxy[j][k];mxd[i]=maxd[j][k];
	}
	Q1.clear();Q2.clear();Q3.clear();
	for(int i=1,j=1;i<R[1];i++)
	{
		for(;j<=t2 && p[j]<=p[i]+H-1;j++)
			if(pre[j]==pre[j-1])
				Q1.push({mny[j],j}),Q2.push({mxy[j],j}),Q3.push({mxd[j],j});
		Q1.pop(i);Q2.pop(i);Q3.pop(i);
		if(pre[j-1]==pre[i-1] && !Q1.empty() && !Q2.empty() && !Q3.empty())
			ans=min(ans,(ll)len+max(Q1.top()+W-Q2.top(),Q3.top())-2);
	}
}
int main()
{
	cin>>H>>W>>n;
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		miny[i][i-1]=1e9;maxy[i][i-1]=-1e9;
		st.clear();st.insert(0);st.insert(W+1);
		for(int j=i;j<=n;j++)
		{
			st.insert(a[j].y);
			miny[i][j]=min(miny[i][j-1],a[j].y);
			maxy[i][j]=max(maxy[i][j-1],a[j].y);
		}
		for(auto it=st.begin();it!=st.end();it++)
			if(next(it)!=st.end()) chkmax(maxd[i][n],*next(it)-*it);
		for(int j=n;j>i;j--)
		{
			auto it=st.find(a[j].y);
			it=st.erase(it);
			maxd[i][j-1]=max(maxd[i][j],*it-*prev(it));
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			if(a[i].x<a[j].x) len[++tot]=a[j].x-a[i].x;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			len[++tot]=a[i].x+H-a[j].x;
	sort(len+1,len+tot+1);
	tot=unique(len+1,len+tot+1)-len-1;
	for(int i=1;i<=tot;i++) solve(len[i]);
	cout<<ans<<endl;
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 2ms
memory: 3772kb

input:

2 4
2
1 1
1 4

output:

3

result:

ok single line: '3'

Test #2:

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

input:

4 1
1
2 1

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

3 3
3
1 2
1 3
3 3

output:

3

result:

ok single line: '3'

Test #4:

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

input:

2 2
1
1 2

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3528kb

input:

4 4
10
4 2
2 3
2 4
4 1
1 2
2 1
4 3
3 3
3 1
1 4

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

4 4
1
4 1

output:

6

result:

ok single line: '6'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

4 4
3
2 2
3 3
1 4

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

4 4
15
4 3
2 4
4 4
4 1
3 3
1 2
3 1
2 1
3 4
3 2
4 2
2 3
1 3
2 2
1 4

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

4 3
3
2 1
2 3
4 1

output:

3

result:

ok single line: '3'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

4 4
2
3 4
2 4

output:

5

result:

ok single line: '5'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3760kb

input:

2 4
1
1 2

output:

4

result:

ok single line: '4'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

3 3
4
2 1
1 1
3 2
3 1

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3368kb

input:

3 4
3
1 4
3 3
3 4

output:

4

result:

ok single line: '4'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

3 3
2
2 1
3 3

output:

4

result:

ok single line: '4'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

4 4
2
2 4
3 1

output:

6

result:

ok single line: '6'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

4 4
3
2 2
2 1
4 2

output:

4

result:

ok single line: '4'

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 10
Accepted
time: 2ms
memory: 3584kb

input:

15 15
20
6 13
14 4
11 13
15 3
12 4
10 4
11 6
8 9
12 12
2 15
4 3
8 15
8 4
3 1
5 10
11 12
8 7
13 10
11 4
1 3

output:

13

result:

ok single line: '13'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3924kb

input:

25 25
66
24 6
12 18
11 2
24 18
6 9
20 6
15 19
17 2
15 9
15 20
18 9
5 19
9 2
6 12
22 16
6 2
1 5
14 24
12 21
17 24
10 15
21 1
20 22
11 24
11 4
6 21
18 12
25 20
16 3
18 16
6 4
20 9
6 15
24 14
3 20
9 9
25 9
18 6
4 16
12 7
14 22
20 25
24 10
11 14
17 6
23 23
21 12
18 22
8 23
1 11
17 18
8 5
3 7
1 17
8 12
4...

output:

9

result:

ok single line: '9'

Test #19:

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

input:

36 38
28
30 5
4 23
29 20
1 36
8 28
8 9
5 26
23 16
26 1
24 38
22 36
4 26
9 7
10 24
20 11
31 5
24 30
26 30
18 15
14 1
23 31
20 7
23 30
33 9
27 33
8 7
9 16
33 5

output:

30

result:

ok single line: '30'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3832kb

input:

10 40
19
7 5
8 38
4 7
8 5
4 30
1 33
1 16
2 21
8 33
4 36
6 20
6 27
4 14
10 15
9 30
8 13
4 15
10 9
5 22

output:

17

result:

ok single line: '17'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3756kb

input:

40 30
50
19 20
18 16
34 28
5 8
28 21
24 13
7 1
28 23
28 18
12 6
3 6
18 8
40 27
22 19
23 22
8 6
9 12
16 10
27 25
26 19
4 9
40 26
21 22
10 8
5 2
30 25
12 12
3 1
24 14
5 3
4 8
19 9
21 16
6 3
38 29
27 20
37 25
36 24
22 20
29 26
30 19
16 14
3 3
39 25
5 7
20 15
13 12
33 30
27 16
25 14

output:

50

result:

ok single line: '50'

Test #22:

score: 0
Accepted
time: 4ms
memory: 4260kb

input:

40 40
120
23 22
31 36
2 4
2 32
14 40
23 32
18 11
27 36
7 1
25 33
22 40
34 9
26 20
18 7
35 7
3 17
19 6
5 27
19 30
33 15
2 15
19 15
4 8
27 1
8 27
10 2
11 39
31 27
32 35
17 4
18 22
2 7
7 10
5 14
40 23
3 36
6 6
6 15
21 35
27 39
25 1
40 11
36 16
8 23
35 27
18 21
24 39
13 22
4 3
12 17
31 16
3 6
6 4
3 30
2...

output:

16

result:

ok single line: '16'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

40 40
33
10 22
10 3
7 11
12 14
11 12
1 21
6 23
3 11
8 24
3 40
8 14
7 25
8 15
12 3
10 7
4 32
7 32
9 32
9 30
4 22
8 22
11 24
6 19
10 16
10 2
9 4
10 15
9 28
7 1
4 31
7 35
4 18
2 35

output:

46

result:

ok single line: '46'

Test #24:

score: 0
Accepted
time: 6ms
memory: 4532kb

input:

40 40
200
10 16
27 15
18 11
16 25
34 7
39 25
26 15
12 20
8 1
20 14
25 27
33 4
29 40
20 33
8 9
32 16
37 25
34 27
31 23
30 8
40 30
35 37
27 7
18 27
36 30
13 30
12 32
32 4
15 21
29 39
4 32
8 7
12 21
35 40
32 29
34 17
22 30
12 34
34 39
23 16
27 16
13 26
28 32
8 31
30 16
13 25
28 13
19 35
38 35
2 40
7 1
...

output:

14

result:

ok single line: '14'

Test #25:

score: 0
Accepted
time: 0ms
memory: 4300kb

input:

40 40
150
8 38
27 32
34 14
29 32
16 36
29 19
40 30
30 22
34 12
4 30
24 37
14 8
31 21
40 17
38 25
16 5
29 5
38 29
28 10
2 5
5 16
20 11
38 6
21 11
5 8
26 13
21 35
27 27
10 11
18 30
30 40
8 18
31 5
16 7
3 1
35 36
40 26
18 39
25 8
19 16
17 26
6 20
13 30
34 4
35 8
33 4
25 29
39 7
22 40
10 36
26 3
30 14
1...

output:

16

result:

ok single line: '16'

Test #26:

score: 0
Accepted
time: 12ms
memory: 5108kb

input:

40 40
300
5 29
4 30
10 5
19 1
11 37
8 26
2 12
29 25
13 33
4 36
15 9
6 39
27 35
34 14
35 27
32 26
14 35
23 35
23 34
12 6
2 21
20 29
20 23
5 21
15 11
7 13
6 23
33 7
19 22
20 31
28 25
7 18
15 39
25 1
2 16
5 23
5 28
7 21
5 31
8 29
16 14
18 29
16 3
3 23
20 35
24 34
14 4
14 30
39 18
25 5
19 37
28 10
7 11
...

output:

18

result:

ok single line: '18'

Test #27:

score: 0
Accepted
time: 9ms
memory: 5112kb

input:

40 40
300
23 5
15 1
34 20
36 22
19 4
31 19
11 34
13 33
3 20
18 4
27 10
37 21
14 11
30 34
8 29
6 26
32 33
8 10
1 14
40 40
4 22
19 31
6 28
37 16
22 34
38 17
16 2
18 36
12 4
38 15
1 24
1 18
32 8
6 18
35 26
12 36
25 2
38 20
19 3
25 12
2 34
35 22
10 36
26 3
10 22
36 8
29 33
3 39
5 10
7 9
36 14
24 5
5 21
...

output:

14

result:

ok single line: '14'

Test #28:

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

input:

39 40
200
9 40
2 33
16 32
14 33
14 27
3 28
5 31
36 30
15 22
23 17
22 28
13 10
4 14
24 35
4 35
12 22
28 32
8 37
7 31
1 37
28 21
39 22
12 17
7 20
35 16
10 12
12 6
27 31
33 15
19 16
13 35
26 35
10 19
15 25
18 19
21 9
11 9
39 4
3 31
20 24
37 26
22 38
13 40
18 12
29 4
31 2
10 26
2 39
2 3
18 9
14 34
39 23...

output:

15

result:

ok single line: '15'

Test #29:

score: 0
Accepted
time: 8ms
memory: 5132kb

input:

38 38
300
30 33
11 38
6 10
19 20
29 30
1 18
30 20
11 19
23 15
32 3
32 30
5 34
7 30
34 1
5 4
20 35
8 13
25 32
12 2
6 3
1 19
38 7
35 16
14 9
37 2
10 4
13 21
37 17
34 4
20 20
14 12
20 13
36 3
10 33
5 8
23 23
9 22
17 19
13 9
20 14
31 4
11 23
17 32
12 10
21 23
31 11
17 35
12 17
31 27
3 6
10 37
2 38
5 15
...

output:

9

result:

ok single line: '9'

Test #30:

score: 0
Accepted
time: 12ms
memory: 5112kb

input:

40 40
300
25 27
25 10
20 19
16 40
29 29
39 20
3 4
6 20
20 6
1 25
39 32
28 26
27 17
30 38
4 33
27 24
21 4
36 32
29 7
4 23
39 2
40 6
14 40
33 39
23 32
23 34
18 6
36 28
40 4
15 28
13 33
34 3
4 35
20 29
38 36
7 24
5 25
20 3
37 13
40 26
5 9
40 36
24 26
16 14
8 28
37 6
24 16
7 3
28 28
34 13
34 36
29 12
13...

output:

10

result:

ok single line: '10'

Test #31:

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

input:

40 40
300
31 12
30 38
21 17
11 12
1 28
10 37
10 13
5 22
18 21
28 37
23 40
29 32
21 33
5 3
21 24
14 15
2 23
9 33
15 31
38 12
37 8
37 26
1 5
28 34
22 10
18 29
30 39
23 34
25 37
35 1
10 7
25 11
10 38
34 30
18 1
12 1
10 25
16 11
35 40
26 30
5 15
23 3
22 22
16 4
8 21
12 23
24 29
4 27
40 5
18 15
35 38
1 1...

output:

9

result:

ok single line: '9'

Test #32:

score: 0
Accepted
time: 12ms
memory: 5224kb

input:

40 40
300
24 6
26 15
30 7
10 12
17 17
7 25
36 26
19 39
32 10
20 1
16 1
34 1
23 19
10 38
40 7
13 39
25 27
28 25
39 18
25 20
17 3
32 28
10 4
6 3
12 16
29 35
13 12
29 16
2 35
6 15
19 7
1 32
18 24
13 18
1 31
28 31
29 12
19 4
20 10
1 3
6 38
1 10
27 14
33 26
1 12
8 31
9 39
22 21
8 39
37 3
26 33
25 10
32 4...

output:

11

result:

ok single line: '11'

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #33:

score: 15
Accepted
time: 11ms
memory: 4904kb

input:

2 200000000
300
1 88265857
1 174408185
1 105379902
1 185252998
2 30206021
2 102367431
2 89739523
1 116153736
2 68837704
1 110817136
2 26646126
2 86276690
1 127329134
2 126441765
1 19927577
1 38738747
1 105161585
1 60367988
2 67085969
1 1865971
1 27164731
1 77127255
2 168438218
1 4482768
1 197852914
...

output:

3425851

result:

ok single line: '3425851'

Test #34:

score: 0
Accepted
time: 6ms
memory: 5124kb

input:

40 1000000000
300
20 483437001
11 245274001
5 80864001
2 7139001
36 895164001
32 773938001
27 666531001
36 894646001
20 467811001
36 877372001
4 76683001
25 599539001
25 604099001
34 834882001
6 105503001
12 279215001
27 655684001
16 364895001
19 439732001
4 61698001
39 973882001
38 925548001
28 684...

output:

19162076

result:

ok single line: '19162076'

Test #35:

score: 0
Accepted
time: 12ms
memory: 5284kb

input:

40 1000000000
300
38 393750001
12 93750001
33 31250002
18 68749999
36 631250003
14 581250003
37 843750003
39 31250001
17 6250002
11 481250000
3 818750001
37 568750002
20 281250001
36 731249999
3 731250003
30 206250000
14 893750002
18 618749999
2 868750003
9 243750003
9 781250000
39 168749999
37 8687...

output:

12500068

result:

ok single line: '12500068'

Test #36:

score: 0
Accepted
time: 12ms
memory: 4988kb

input:

40 1000000000
300
20 273611973
30 962515424
19 457562756
14 228419368
9 839242624
34 416448186
6 49326057
27 373662328
18 43718671
40 180109032
35 703858821
6 62818768
23 176704786
30 419420243
29 966647309
30 971207395
9 471992569
17 18782375
28 524707582
15 887562815
20 339788418
40 188122260
33 1...

output:

25840886

result:

ok single line: '25840886'

Test #37:

score: 0
Accepted
time: 6ms
memory: 5112kb

input:

35 1000000000
300
26 304985784
31 53820856
34 188129610
32 933853739
29 435634084
16 233290946
24 581180249
14 763935773
10 265931834
9 274498426
16 675425485
15 87227536
21 985415295
14 272012946
12 765102757
24 458857877
20 610373170
25 928877042
32 589674594
23 467914943
31 693779625
19 197133223...

output:

14686151

result:

ok single line: '14686151'

Test #38:

score: 0
Accepted
time: 12ms
memory: 5124kb

input:

40 1000000000
300
6 786763464
27 418721225
37 714875337
10 156646263
9 190541536
30 429336661
7 865464196
28 815774814
35 25779712
30 681279351
11 395942851
13 574687654
29 137106802
33 754832787
37 294845778
19 815900516
14 704212093
36 198711902
17 533523161
34 748841831
17 981957453
30 294955278
...

output:

21233330

result:

ok single line: '21233330'

Test #39:

score: 0
Accepted
time: 12ms
memory: 5188kb

input:

40 1000000000
300
40 70731728
31 860477266
8 270731733
14 56097551
5 524390251
21 148780485
6 60975598
26 612195132
13 997560998
36 426829256
32 7317081
1 256097581
25 457312359
12 241463431
5 85365829
18 4440737
1 436585368
34 39238855
33 625252064
1 143902436
13 338440011
25 334146355
5 515606983
...

output:

4878171

result:

ok single line: '4878171'

Test #40:

score: 0
Accepted
time: 12ms
memory: 5128kb

input:

40 1000000000
300
34 290272040
11 654139182
15 574182947
32 483616706
23 30659851
7 688206175
33 677483533
20 245930698
16 854673531
5 415424827
23 516937655
2 347957583
4 76422831
29 693454243
24 109103102
19 755284863
16 509051878
8 373221893
35 422824677
1 923039234
37 493392984
2 648194620
12 12...

output:

23360164

result:

ok single line: '23360164'

Test #41:

score: 0
Accepted
time: 11ms
memory: 5312kb

input:

40 999992811
300
40 756167738
1 755422093
1 756075552
40 755448533
40 755699260
1 755699433
40 756570280
40 755364761
1 755246371
40 756081840
1 756154293
1 756152536
1 755866341
1 755312497
40 755640274
7 340135464
3 953017751
1 755712914
1 755664483
40 755797029
9 969531054
40 755779575
1 75564995...

output:

129414313

result:

ok single line: '129414313'

Test #42:

score: 0
Accepted
time: 12ms
memory: 5332kb

input:

40 1000000000
300
17 999998001
1 999997965
1 999997890
1 7932
5 505323503
40 999998121
1 999998027
1 999998002
9 999997972
1 999997920
40 999997891
30 7999
29 7999
31 999998062
1 999998144
40 999997890
40 999998033
1 999998006
21 999997999
40 999998031
40 8094
40 999997995
13 999998024
40 999997875
...

output:

209640461

result:

ok single line: '209640461'

Test #43:

score: 0
Accepted
time: 12ms
memory: 5180kb

input:

40 1000000000
300
23 549509844
40 95786908
40 39290135
13 992491098
26 87052294
40 231331522
19 288109792
23 482918072
1 27192653
25 931473083
40 1
12 695623563
8 518257580
1 40343403
40 271412132
40 24291430
1 776119616
29 837580112
5 24636122
2 883373187
31 209930451
37 133788324
1 224219724
1 138...

output:

21898080

result:

ok single line: '21898080'

Test #44:

score: 0
Accepted
time: 8ms
memory: 5224kb

input:

40 1000000000
300
6 366666665
15 300000001
24 233333337
1 966666667
25 853754960
23 766666669
30 233333334
24 433333334
15 566666670
14 233333334
34 233333335
32 166666668
37 366666664
30 337173509
30 100000002
31 33333334
17 500000004
15 834459573
22 773895258
32 900000001
35 100000002
40 500000001...

output:

53549258

result:

ok single line: '53549258'

Subtask #4:

score: 30
Accepted

Test #45:

score: 30
Accepted
time: 2ms
memory: 3716kb

input:

1000000000 1000000000
17
822413671 70423910
260075513 431043546
300945721 793553248
142848049 163787897
392462410 831950868
699005697 111397300
444396260 130450496
642691616 595456084
467968916 463598810
159764248 611476406
929313754 539645102
365153650 964108073
906780716 373514044
970118116 655138...

output:

852626202

result:

ok single line: '852626202'

Test #46:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

1000000000 1000000000
24
382358372 812500277
617637090 687506454
441176760 562497727
382346048 687504690
205880053 312504652
794110577 62497634
264714161 937490675
970587944 812502893
617647581 62504110
852944701 812498007
88227293 187492617
558814156 687495577
29403236 812494493
911761865 187491781...

output:

904419459

result:

ok single line: '904419459'

Test #47:

score: 0
Accepted
time: 3ms
memory: 3668kb

input:

1000000000 1000000000
25
59999964 299999989
740000035 100000111
139999972 499999797
740000159 899999809
940000104 899999905
459999870 299999853
139999925 899999750
260000183 300000150
260000200 699999915
940000072 99999821
340000223 900000130
739999776 499999813
59999984 700000029
539999767 90000023...

output:

480000793

result:

ok single line: '480000793'

Test #48:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

1000000000 1000000000
25
496770868 499466029
150245306 140351260
443861207 442170127
915815913 907024280
592352731 580300173
614771420 602707761
545759771 564678204
790963611 795646738
466306333 474998682
700037062 710428701
326403486 341417980
13108429 18468915
296795338 282907012
207909366 2192548...

output:

1967193239

result:

ok single line: '1967193239'

Test #49:

score: 0
Accepted
time: 3ms
memory: 3624kb

input:

1000000000 1000000000
25
508699723 917649746
972134563 24654272
591574312 768222747
342111766 678842208
280650655 335101574
112108587 538128714
232733100 741988808
569340416 313541403
333183415 646381341
348331220 239049882
321253252 46884019
458715217 456559440
11396102 588839952
212356188 55359081...

output:

967430445

result:

ok single line: '967430445'

Test #50:

score: 0
Accepted
time: 3ms
memory: 3672kb

input:

1000000000 1000000000
25
87500002 928571428
712500002 71428571
212500002 71428570
837500001 71428573
912499999 214285715
287500002 785714285
37500003 785714285
962500002 357142856
787500000 785714288
787500003 500000003
462500002 71428570
462500001 357142859
37499999 500000000
462500002 642857144
37...

output:

660714282

result:

ok single line: '660714282'

Test #51:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

1000000000 1000000000
25
499999999 565789472
499999990 250000002
499999996 749999995
499999999 144736850
499999993 513157893
499999992 644736853
500000010 13157889
499999998 118421056
499999993 197368414
499999990 592105269
499999994 486842107
500000005 276315783
499999994 539473685
499999990 618421...

output:

1131578975

result:

ok single line: '1131578975'

Test #52:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

999999999 777777777
25
777772259 317438734
467526694 324943812
750092374 316807230
351488629 328182224
670366487 319838016
194662876 330078646
807706262 316391102
682779230 318750710
529347725 323684686
437218310 325726470
284055780 328324426
156380921 332766879
754204172 318252081
631742119 3197068...

output:

1086358403

result:

ok single line: '1086358403'

Test #53:

score: 0
Accepted
time: 2ms
memory: 3524kb

input:

100000000 1000000000
25
75997424 820728673
777782 777777776
777783 777777777
777780 777777778
18626903 845305698
32700264 518597334
66223561 813120928
92237121 497548369
66359837 477082113
51360029 493816356
777776 777777775
777778 777777776
77907935 347786430
777776 777777776
777779 777777786
77777...

output:

434734665

result:

ok single line: '434734665'

Test #54:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

1000000000 1000000000
25
202384720 191386798
272784910 876112960
134295596 689831109
144607550 725288401
304962179 141608855
184056836 214149818
580684614 928741905
339656490 906353399
222518718 825019927
65386126 415917878
836363213 211099284
885557581 342429798
772605154 167160669
750597218 865168...

output:

1169492481

result:

ok single line: '1169492481'

Test #55:

score: 0
Accepted
time: 3ms
memory: 3592kb

input:

1000000000 1000000000
25
217898725 381443931
363716745 553078122
741451918 906975033
153568070 900704450
12302872 385341608
276235760 349179186
221511192 438759684
177246208 108385423
157609379 88135252
542559523 122476619
676920172 289023879
132864371 527493734
980440215 892433157
465353007 9681278...

output:

936384704

result:

ok single line: '936384704'

Test #56:

score: 0
Accepted
time: 3ms
memory: 3704kb

input:

1000000000 1000000000
25
108777360 996968244
655575871 74556270
426116462 624297074
601010849 48108108
411143918 863537296
176018437 125264437
769284398 653206473
823951690 375380635
675138657 124417631
305117857 433890179
878598110 72028431
322847356 902439915
323815174 873868901
575209775 37455562...

output:

603034352

result:

ok single line: '603034352'

Test #57:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

335563010 332545567
25
106441293 332545567
117303130 332545567
335563010 272104540
335563010 47336793
335563010 171741328
315104367 332545567
335563010 258033462
174568335 332545567
170964494 332545567
335563010 68594399
304935196 332545567
97310526 332545567
99941575 332545567
12373018 332545567
33...

output:

389908846

result:

ok single line: '389908846'

Test #58:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

1000000000 1000000000
25
786394982 791216768
119431195 847633609
81087720 1
264330507 432964753
737246186 427050407
922213406 555980523
550982306 581735630
1 1
852080288 1
1 538609505
375220500 773780706
182457491 294843990
1 634980243
421417169 1
253676052 1
601408832 610485554
957268112 249030717
...

output:

905880429

result:

ok single line: '905880429'

Test #59:

score: 0
Accepted
time: 2ms
memory: 3720kb

input:

1000000000 999999999
25
123456824 987654308
123456819 987654326
123456769 987654289
123456790 987654288
123456802 987654292
123456810 987654352
123456754 987654338
123456799 987654354
123456821 987654331
123456812 987654344
123456754 987654308
123456771 987654347
123456759 987654325
123456794 987654...

output:

1999999906

result:

ok single line: '1999999906'

Test #60:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

800000000 850000000
25
335835504 189725436
12182937 480593240
63284654 46903085
328812657 436279057
477372871 828400687
194405795 653579540
710586790 72905770
723953376 117573812
64734838 462492145
171374113 120671772
209599317 71273938
194054608 171593430
167629250 52680425
14966053 566230223
12058...

output:

802951025

result:

ok single line: '802951025'

Test #61:

score: 0
Accepted
time: 4ms
memory: 3668kb

input:

1000000000 1000000000
25
62157117 656205518
713439094 288906525
164961619 102056326
876566497 377063232
495641022 967020329
945382229 113881584
172072381 293104404
486897712 389281101
737647745 678839821
248637273 650807852
952485639 634170837
833476502 432041466
148863447 117321892
496035975 546217...

output:

922368183

result:

ok single line: '922368183'

Test #62:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

1000000000 1000000000
25
499999980 343399132
499999906 225597526
500000007 861547250
499999909 461896002
500000078 691034441
499999919 222514427
499999978 236039953
500000027 612489620
500000050 614406498
500000052 169059154
500000075 102616793
500000005 334144037
500000097 500336043
499999996 14731...

output:

1241069609

result:

ok single line: '1241069609'

Test #63:

score: 0
Accepted
time: 3ms
memory: 3720kb

input:

1000000000 1000000000
25
642065222 981136342
121675139 261963018
735944627 576109400
338153502 307800112
679432262 331837809
40070650 210942580
817625196 535344408
789427854 731652674
774571963 608761006
114198549 290605105
755781608 320483327
257969748 129605173
627155257 309519841
485229109 512450...

output:

939246082

result:

ok single line: '939246082'

Test #64:

score: 0
Accepted
time: 3ms
memory: 3664kb

input:

1000000000 1000000000
25
611076895 363884544
439305553 342413208
438525493 342315624
208146420 313518360
433276048 341659421
891567968 398946036
554628049 356828591
182192780 310274086
713718510 376714855
248891223 318611451
184804702 310600627
197198331 312149761
834859186 391857364
737551904 37969...

output:

1379296760

result:

ok single line: '1379296760'

Subtask #5:

score: 20
Accepted

Dependency #4:

100%
Accepted

Test #65:

score: 20
Accepted
time: 35ms
memory: 3912kb

input:

1000000000 1000000000
100
687499990 187500017
691054532 301146309
937499988 312500002
687499994 937500007
579878939 781071766
187500018 562500000
187500009 937500018
562499999 562500008
562499985 687499991
562500019 937500016
62499982 562499999
937500012 812500017
62499989 687500003
812499999 937500...

output:

250000064

result:

ok single line: '250000064'

Test #66:

score: 0
Accepted
time: 60ms
memory: 4152kb

input:

1000000000 1000000000
100
542839344 460784175
764577804 73469018
973053355 582110240
227275321 887279728
877462957 6335451
123071062 183008573
75817935 385158033
531903085 153788001
567541302 401895176
684722196 789303723
859433169 221358091
265925767 758747732
801564400 623065017
813697484 56178464...

output:

443169563

result:

ok single line: '443169563'

Test #67:

score: 0
Accepted
time: 67ms
memory: 4184kb

input:

1000000000 1000000000
100
441418843 100271521
447977823 105427459
445102973 99698689
450318271 892850747
441382754 104692662
444894142 891456864
445508202 92700655
438105177 99180605
449203792 890578392
450212270 96714613
443535131 887141139
443955088 98197899
443858332 892648803
443973287 95210209
...

output:

1772795142

result:

ok single line: '1772795142'

Test #68:

score: 0
Accepted
time: 58ms
memory: 3996kb

input:

1000000000 1000000000
100
889156435 714438618
889336408 715294191
888939803 715213403
99924877 744916962
889209500 715138550
888803546 714984297
889117445 714588559
888991575 715053554
888715509 715011760
889190571 714877644
888866677 715230384
889175860 714939055
888533104 715170413
888882048 71528...

output:

1817622448

result:

ok single line: '1817622448'

Test #69:

score: 0
Accepted
time: 64ms
memory: 4000kb

input:

1000000000 1000000000
100
700015829 795702538
841987573 597503842
864879088 817375719
290149922 819983410
525506660 60963665
867074117 382441617
556493999 830774423
193560596 616455758
706396769 403076992
852912726 705506780
10222864 118710353
927780780 554649635
512547641 663935246
11968287 5685054...

output:

469662017

result:

ok single line: '469662017'

Test #70:

score: 0
Accepted
time: 23ms
memory: 4192kb

input:

900000000 800000000
100
539328722 46933087
1 346231212
7996497 1
319791651 800000000
540027394 800000000
15682268 800000000
65965842 752502190
1 94613470
341707243 800000000
604531347 1
662868480 1
842989035 800000000
447334492 1
747654645 800000000
1 395951805
376289914 54497461
900000000 181873065...

output:

695557539

result:

ok single line: '695557539'

Test #71:

score: 0
Accepted
time: 60ms
memory: 3784kb

input:

1000000000 1000000000
100
576019722 576731254
34534933 41532354
312314245 314683319
785390133 783036403
702745349 699472167
561033586 568534716
983913351 967266069
637833123 630909512
118291167 118507843
775681461 786122038
340629086 351626639
234556649 237767341
777128793 778128856
857203596 861263...

output:

1966119009

result:

ok single line: '1966119009'

Test #72:

score: 0
Accepted
time: 62ms
memory: 4088kb

input:

1000000000 1000000000
100
928726043 764696650
375580170 418961839
371082575 132195766
867406178 756269836
653572760 38349187
686531294 398976045
48971801 719850555
993778576 4599956
843584800 678738510
98689299 840256129
989208023 741632477
462911847 443376132
160038550 890566730
765304836 455418643...

output:

476666857

result:

ok single line: '476666857'

Test #73:

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

input:

1000000000 1000000000
100
855090718 688743004
656729697 988798850
355808853 386266222
341590297 423952911
156130053 756093340
850385829 149630244
858212777 287892688
359305700 682324504
159865123 815937328
143876512 185691060
146370821 599761929
648804157 621881128
344064714 309618221
858715171 9513...

output:

459823110

result:

ok single line: '459823110'

Test #74:

score: 0
Accepted
time: 58ms
memory: 4088kb

input:

1000000000 1000000000
100
726843076 10351859
879584139 373974016
267852562 286736200
195897212 829647899
715832751 875977818
256939347 275942632
958681194 351640246
270998650 667371737
875265447 325319774
201342012 734623861
891268004 4380005
584955939 236756645
81478727 440361456
74399820 988266596...

output:

585564003

result:

ok single line: '585564003'

Test #75:

score: 0
Accepted
time: 62ms
memory: 3848kb

input:

1000000000 1000000000
100
302873638 802518331
747916007 292283372
33204420 608466457
181499312 656928875
477590903 829513066
294341038 191147120
62798904 934216151
805380371 18054353
626190333 400064953
583470503 299444677
61994876 946533850
910863880 13769746
255232847 874165619
894912702 619240949...

output:

441778875

result:

ok single line: '441778875'

Test #76:

score: 0
Accepted
time: 60ms
memory: 3924kb

input:

1000000000 1000000000
100
236566110 841588240
681365516 361560437
935140887 787880578
697623224 646531137
928787811 574232374
753948476 564133161
729408758 49489242
134648810 601310133
247857070 547588190
99310384 1
762083013 896494859
180155077 424178075
798198008 732288381
631034756 234183726
3838...

output:

521454223

result:

ok single line: '521454223'

Test #77:

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

input:

1000000000 1000000000
100
407924149 158482998
415653252 313065009
414573396 291467995
404592394 91848000
407887995 157760009
448507142 970142998
434054396 681087995
426407950 528159006
413020058 260400991
444243391 884867999
425548649 510972996
430696943 613939011
440650400 813007998
417158698 34317...

output:

1100915441

result:

ok single line: '1100915441'

Test #78:

score: 0
Accepted
time: 60ms
memory: 4088kb

input:

1000000000 1000000000
100
701998381 577124106
461439742 586008343
249356290 589118161
864208917 557567966
914931852 523146821
815537467 572000631
709526887 548834485
358235176 576942817
715074556 556481868
425174418 585446103
699181337 541462104
345211883 601918838
524645242 593291133
663191990 5779...

output:

1165842671

result:

ok single line: '1165842671'

Test #79:

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

input:

1000000000 1000000000
100
862711011 601927729
332635154 545321423
362241452 587307633
30116310 749597564
108582181 678550664
637474925 616430433
784359776 507999280
666869305 572184078
87637252 704457737
608134832 664285946
744635776 500682999
589132939 692882132
489742075 745400199
725204188 508695...

output:

1200231273

result:

ok single line: '1200231273'

Test #80:

score: 0
Accepted
time: 67ms
memory: 4164kb

input:

1000000000 1000000000
100
323283210 323625382
323146201 539174425
749914073 431427761
499953095 294163192
676735265 441216105
323280988 950941540
676800293 911723177
676863159 421639904
676776904 519566414
249932831 862836353
323167901 166751639
499910407 333269241
750071818 196099488
499971585 6470...

output:

637550138

result:

ok single line: '637550138'

Subtask #6:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #81:

score: 20
Accepted
time: 641ms
memory: 4456kb

input:

1000000000 1000000000
220
478305022 575498457
817530337 573058380
226672256 322382005
707862483 701168514
59898277 240479737
767851183 832518979
789480310 832859987
979455621 978326001
233198216 783681900
897099316 556630905
133322287 268045093
992346636 982124202
525157607 950535312
306146309 42991...

output:

366316521

result:

ok single line: '366316521'

Test #82:

score: 0
Accepted
time: 655ms
memory: 4832kb

input:

1000000000 1000000000
220
683473761 57443518
242404737 345579136
279061086 641382071
223484389 386631315
256278002 873680320
35175009 770659371
234849397 538394078
838829456 166261009
159071183 371915413
366518273 695797309
959602482 527099601
920572927 966717452
886131750 190612442
961083592 987227...

output:

377081435

result:

ok single line: '377081435'

Test #83:

score: 0
Accepted
time: 753ms
memory: 4892kb

input:

1000000000 1000000000
250
93751048 972224499
281249088 972221584
468751817 861111372
656247695 83332078
343749391 305557550
406251075 694446945
406251653 83331580
531249180 527778996
343749007 583335438
968750695 250001727
281252417 861111339
343748323 472221491
906249071 750000275
156252313 1388873...

output:

236115469

result:

ok single line: '236115469'

Test #84:

score: 0
Accepted
time: 924ms
memory: 4848kb

input:

75000000 1000000000
250
23316123 689228671
51460363 313800462
46919590 374430210
21268052 716388845
30798665 589243439
36208076 517156033
7103035 905224685
48721212 350328117
20606954 725216029
49273750 342959560
67863784 95213473
53508347 286584259
1301237 982696818
29722012 603821394
41965640 4404...

output:

166268834

result:

ok single line: '166268834'

Test #85:

score: 0
Accepted
time: 1611ms
memory: 5124kb

input:

1000000000 1000000000
300
489444377 431939746
142205808 841027480
331675582 250133892
721126188 22536053
15604339 249996314
647397107 795553008
15740205 977191518
752490509 68278790
15963751 704503527
773555723 386365635
194769253 22608742
352543648 113658446
279132570 158942372
405123623 931886012
...

output:

262671212

result:

ok single line: '262671212'

Test #86:

score: 0
Accepted
time: 1514ms
memory: 5132kb

input:

1000000000 1000000000
300
412498171 380003087
537496683 219997896
962500905 99996916
827271748 230684769
962501779 899997571
861779255 265685841
162500039 59999637
912498010 620000013
686236349 973984207
870751679 359652877
162500427 139999018
337502509 259999507
587499610 979997913
587498075 199994...

output:

195010944

result:

ok single line: '195010944'

Test #87:

score: 0
Accepted
time: 1080ms
memory: 5292kb

input:

1000000000 1000000000
300
564885012 1000000000
960344127 628681258
408158680 909851834
858122662 770560758
836212426 1000000000
796166987 1000000000
684551326 689258793
416185912 636561293
598461411 196180912
75540237 144389694
239223463 445707890
4393274 1000000000
527186628 985033799
940721129 523...

output:

363328021

result:

ok single line: '363328021'

Test #88:

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

input:

1000000000 1000000000
300
649963070 290637344
636900531 292875466
725479435 877723400
637477522 290459324
645953614 288126652
641573271 294894479
728867965 867779815
642092094 282545806
721327347 878784340
639139124 289691970
646492211 289748504
726486819 879636082
650820317 287336194
648818361 2844...

output:

1630591892

result:

ok single line: '1630591892'

Test #89:

score: 0
Accepted
time: 1686ms
memory: 5292kb

input:

1000000000 1000000000
300
447271183 771371438
546453048 783832140
523400559 251948896
261133909 282170737
158686642 512613459
691882468 498062481
346100907 380521374
730526849 300506795
708978699 764961497
682873633 715841773
773397405 582233116
273991044 320348239
426979181 395670514
596869414 3964...

output:

1096148278

result:

ok single line: '1096148278'

Test #90:

score: 0
Accepted
time: 1091ms
memory: 5036kb

input:

1000000000 1000000000
270
320165296 422794443
609592718 290440943
259684890 474264413
250151960 507353247
737764218 867647283
251369552 492646934
748630802 823529250
526132124 18382324
639798549 275735500
332717317 591911941
268203818 463235209
737763863 205882548
731795706 213235573
568909540 36764...

output:

1316049371

result:

ok single line: '1316049371'

Test #91:

score: 0
Accepted
time: 1617ms
memory: 5144kb

input:

1000000000 1000000000
300
89111389 37728758
120066788 179857003
53081938 1000000000
764428917 81671350
761138917 893276950
402530202 286836610
468315104 680670034
559595380 159656530
603245842 899043578
833602260 225037560
621937816 354426593
481322495 296058160
388180181 180428732
269599881 8507481...

output:

369339293

result:

ok single line: '369339293'

Test #92:

score: 0
Accepted
time: 1657ms
memory: 5200kb

input:

1000000000 1000000000
300
723427119 549989197
77653871 979154067
404263692 594042440
977725437 977857876
831816449 513792760
468126859 78347772
343867856 92477825
970991291 166095630
399104927 381485928
712304339 5403707
364857674 712837290
752581187 237490062
860177308 465935555
513235024 860313660...

output:

324195650

result:

ok single line: '324195650'

Test #93:

score: 0
Accepted
time: 1597ms
memory: 5396kb

input:

1000000000 1000000000
300
832654398 518518278
258276604 432819206
210373958 465433190
250055641 454774351
837469016 497820440
263617242 429448413
863135450 533101273
763128128 495615230
262402455 459978191
271191170 389712758
893939902 437312000
872064127 598037898
293935751 462058106
853473205 5405...

output:

1390293729

result:

ok single line: '1390293729'

Test #94:

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

input:

1000000000 1000000000
300
152221306 651266490
549609936 260790685
768298483 526028939
470159135 255406477
394003873 307366142
778203989 541669871
943587732 734219730
400640689 300958797
834404366 625079897
698732728 417734209
655538313 357204221
930378947 726275854
52939845 739336148
453686976 26224...

output:

1393015565

result:

ok single line: '1393015565'

Test #95:

score: 0
Accepted
time: 1660ms
memory: 5052kb

input:

1000000000 1000000000
300
588058789 126000591
624287477 84503152
690977116 930510312
74997 967071460
12388671 571617097
148319486 122071265
243267687 7099503
620965 610944920
226793153 350753118
724623314 722266940
902108205 285852902
252799973 833357388
219452752 176946093
563648851 233519804
20181...

output:

350785247

result:

ok single line: '350785247'

Test #96:

score: 0
Accepted
time: 1634ms
memory: 5056kb

input:

1000000000 1000000000
300
366003065 547388724
66010721 846388591
56422327 860263681
343609652 220257104
68140440 865071553
992292399 288892540
755704172 293323234
59716704 864269456
56223540 853128739
868129719 44817009
47047186 861666640
849704221 971878631
66349889 870549974
333543520 826067542
51...

output:

493082045

result:

ok single line: '493082045'

Test #97:

score: 0
Accepted
time: 1588ms
memory: 5140kb

input:

1000000000 1000000000
300
388694842 555568635
199338847 555555337
212631261 555563935
196004385 555550036
591356646 444456869
225926198 555544180
219253802 555553225
348851426 555551943
750816199 444454500
624578086 444458617
282403542 555550243
372106165 555543016
265795800 555549443
66438129 55556...

output:

1117794068

result:

ok single line: '1117794068'

Test #98:

score: 0
Accepted
time: 11ms
memory: 5100kb

input:

1000000000 1000000000
300
454545452 840531559
454545454 528239200
545454543 249169433
454545456 837209300
454545455 943521594
454545456 541528240
545454544 305647842
454545455 598006643
454545455 534883718
454545454 970099665
454545452 883720928
454545454 953488371
454545453 561461794
454545455 5946...

output:

1097553613

result:

ok single line: '1097553613'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-02 04:49:55 | OpenSource Project