QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211681#360. CultivationRafi22#30 219ms3920kbC++141.9kb2023-10-12 20:18:362024-07-04 02:19:26

Judging History

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

  • [2024-07-04 02:19:26]
  • 评测
  • 测评结果：30
  • 用时：219ms
  • 内存：3920kb
查看
  • [2023-10-12 20:18:36]
  • 提交

answer

#include <bits/stdc++.h>

#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
int mod=1000000007;
int mod1=998244353;

const int N=307;

int r,c,n;
int ans=inf;

int x[N],y[N];

void check(int U,int D)
{
    set<pair<int,int>>X;
    vector<pair<int,int>>E;
    int S=0,L=0,R=0;
    for(int i=1;i<=n;i++)
    {
        if(max(1LL,x[i]-D)==1) X.insert({y[i],i});
        else E.pb({max(1LL,x[i]-D),-i});
        if(min(r,x[i]+U)<r) E.pb({min(r,x[i]+U)+1,i});
    }
    if(sz(X)==0) return ;
    R=(*X.begin()).st-1;
    L=c-(*--X.end()).st;
    int last=-1;
    for(auto [Y,i]:X)
    {
        if(last!=-1) S=max(S,Y-last-1);
        last=Y;
    }
    X.insert({-inf,0});
    X.insert({inf,0});
    sort(all(E));
    for(auto [t,i]:E)
    {
        if(i<0) X.insert({y[-i],-i});
        else
        {
            X.erase({y[i],i});
            if(sz(X)==2) return ;
            int LL=(*--X.upper_bound({y[i],0})).st;
            int RR=(*X.upper_bound({y[i],0})).st;
            if(LL==-inf) R=max(R,RR-1);
            if(RR==inf) L=max(L,c-LL);
            if(LL!=-inf&&RR!=inf) S=max(S,RR-LL-1);
        }
    }
    ans=min(ans,U+D+max(S,R+L));
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>r>>c>>n;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    set<int>cnd;
    cnd.insert(0);
    for(int i=1;i<=n;i++)
    {
        cnd.insert(x[i]-1);
        cnd.insert(r-x[i]);
        for(int j=1;j<=n;j++) cnd.insert(abs(x[i]-x[j])-1);
    }
    for(auto i:cnd) for(auto j:cnd) check(i,j);
    cout<<ans;




    return 0;
}
/*
4 4
4
1 1
1 4
4 1
4 4
*/
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: 0ms
memory: 3568kb

input:

2 4
2
1 1
1 4

output:

3

result:

ok single line: '3'

Test #2:

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

input:

4 1
1
2 1

output:

3

result:

ok single line: '3'

Test #3:

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

input:

3 3
3
1 2
1 3
3 3

output:

3

result:

ok single line: '3'

Test #4:

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

input:

2 2
1
1 2

output:

2

result:

ok single line: '2'

Test #5:

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

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: 0ms
memory: 3564kb

input:

4 4
1
4 1

output:

6

result:

ok single line: '6'

Test #7:

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

input:

4 4
3
2 2
3 3
1 4

output:

5

result:

ok single line: '5'

Test #8:

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

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: 0ms
memory: 3564kb

input:

4 3
3
2 1
2 3
4 1

output:

3

result:

ok single line: '3'

Test #10:

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

input:

4 4
2
3 4
2 4

output:

5

result:

ok single line: '5'

Test #11:

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

input:

2 4
1
1 2

output:

4

result:

ok single line: '4'

Test #12:

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

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: 0ms
memory: 3596kb

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: 3556kb

input:

3 3
2
2 1
3 3

output:

4

result:

ok single line: '4'

Test #15:

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

input:

4 4
2
2 4
3 1

output:

6

result:

ok single line: '6'

Test #16:

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

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: 1ms
memory: 3624kb

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: 8ms
memory: 3576kb

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: 4ms
memory: 3868kb

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: 0ms
memory: 3628kb

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: 10ms
memory: 3628kb

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: 41ms
memory: 3592kb

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: 2ms
memory: 3644kb

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: 77ms
memory: 3536kb

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: 55ms
memory: 3556kb

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: 122ms
memory: 3712kb

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: 126ms
memory: 3620kb

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: 75ms
memory: 3648kb

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: 112ms
memory: 3872kb

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: 119ms
memory: 3608kb

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: 121ms
memory: 3648kb

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: 126ms
memory: 3624kb

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: 1ms
memory: 3604kb

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: 90ms
memory: 3616kb

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: 123ms
memory: 3624kb

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: 117ms
memory: 3612kb

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: 94ms
memory: 3920kb

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: 121ms
memory: 3684kb

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: 122ms
memory: 3556kb

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: 121ms
memory: 3620kb

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: 93ms
memory: 3612kb

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: 111ms
memory: 3604kb

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: 117ms
memory: 3568kb

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: 126ms
memory: 3600kb

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: 0
Wrong Answer

Test #45:

score: 30
Accepted
time: 26ms
memory: 3632kb

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: 174ms
memory: 3836kb

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: 186ms
memory: 3616kb

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: -30
Wrong Answer
time: 219ms
memory: 3644kb

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:

1000000007

result:

wrong answer 1st lines differ - expected: '1967193239', found: '1000000007'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%
English 繁體中文 简体中文

Server Time: 2024-11-29 16:46:06 | OpenSource Project