QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234788#2295. Dyson CircleCodeZhazgyshAC ✓100ms34428kbC++143.1kb2023-11-01 22:27:412023-11-01 22:27:41

Judging History

This is the latest submission verdict.

  • [2023-11-01 22:27:41]
  • Judged
  • Verdict: AC
  • Time: 100ms
  • Memory: 34428kb
  • [2023-11-01 22:27:41]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
void ans()
{
    //freopen("input","r",stdin);
    //freopen("output","w",stdout);
    ll n,chec = 0;cin>>n;
    vector<ll> minn(2e6+1,1e18);
    vector<ll> maxx(2e6+1,-1e18);
    ll left = 1e18;
    ll right = -1e18;
    ll mi = 1e18,ma = -1e18;
    ll passed = 0,o = 0,checked = 0;
    for (ll w = 0;w<n;w++)
    {
        ll a,b;cin>>a>>b;
        b+=1e6;
        a+=1e6;
        minn[a] = min(minn[a],b);
        maxx[a] = max(maxx[a],b);
        mi = min(mi,b);
        ma = max(ma,b);
        left = min(left,a);
        right = max(right,a);
    }
    ll y = minn[left];
    ll answer = 2;
    bool reached = 0;
    bool done = 0;
    for (ll e = left-1;e<right;e++)
    {
        // cout<<y-1e6<<" ";
        if (reached)
        {
            if (passed == 1)
            {
                answer++;
                passed++;
                done = 1;
                continue;
            }
            if (minn[e+1] < y)
            {
                chec = 1;
                y = minn[e+1]-1;
            }
            else 
            {
                y++;
                if (y >= minn[e+1]) 
                {
                    chec = 1;
                    y = minn[e+1]-1;
                }
            }
            answer++;
        }
        else if (minn[e+1] >= y)
        {
            y--;
            answer++;
        }
        else 
        {
            checked = 1;
            if (done)
            {
                done = 0;
                o = 1;
            }
            answer+=y-minn[e+1]+1;
            y = minn[e+1]-1;
        }
        if (y < mi)
        {
            reached = 1;
        }
        passed++;
    }
    // cout<<y-1e6<<"\n";
    passed = 0;
    answer+=minn[right]-y-1;
    ll x = y;
    y = minn[left];
    reached = 0;
    for (ll e = left-1;e<right;e++)
    {
        // cout<<y-1e6<<" ";
        if (reached)
        {
            if (passed == 1 && !checked)
            {
                done = 1;
                answer++;
                passed++;
                continue;
            }
            if (maxx[e+1] > y)
            {
                chec = 1;
                y = maxx[e+1]+1;
            }
            else 
            {
                y--;
                if (y <= maxx[e+1]) 
                {
                    chec = 1;
                    y = maxx[e+1]+1;
                }
            }
            answer++;
        }
        else if (maxx[e+1] <= y)
        {
            y++;
            answer++;
        }
        else 
        {
            if (done)
            {
                done = 0;
                o = 1;
            }
            answer+=maxx[e+1]-y+1;
            y = maxx[e+1]+1;
        }
        if (y > ma)
        {
            reached = 1;
        }
        passed++;
    }
    // cout<<y-1e6<<"\n";
    if (!chec)
    {
        answer-=o;
    }
    answer+=y-minn[right]-1;
    cout<<answer;
}
int main()
{
    ll t =1;
    while (t--)
    {
        ans();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 34368kb

input:

1
-201504 -209794

output:

4

result:

ok single line: '4'

Test #2:

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

input:

2
23 42
24 43

output:

7

result:

ok single line: '7'

Test #3:

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

input:

2
23 42
24 41

output:

7

result:

ok single line: '7'

Test #4:

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

input:

2
-1000000 -1000000
1000000 1000000

output:

4000005

result:

ok single line: '4000005'

Test #5:

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

input:

2
1000000 -1000000
-1000000 1000000

output:

4000005

result:

ok single line: '4000005'

Test #6:

score: 0
Accepted
time: 5ms
memory: 34340kb

input:

2
-1000000 -1000000
1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #7:

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

input:

2
-1000000 -1000000
999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #8:

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

input:

2
1000000 -1000000
-1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #9:

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

input:

2
1000000 -1000000
-999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #10:

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

input:

2
4711 -1000000
4711 1000000

output:

4000004

result:

ok single line: '4000004'

Test #11:

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

input:

2
1000000 4711
-1000000 4711

output:

4000004

result:

ok single line: '4000004'

Test #12:

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

input:

7
-53 94
-71 20
-93 -75
62 30
-90 36
22 -45
-17 -28

output:

478

result:

ok single line: '478'

Test #13:

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

input:

3
66 -48
-97 45
63 -70

output:

349

result:

ok single line: '349'

Test #14:

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

input:

1
-77 10

output:

4

result:

ok single line: '4'

Test #15:

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

input:

4
60 83
20 -33
-69 51
54 -60

output:

399

result:

ok single line: '399'

Test #16:

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

input:

4
2 70
66 -44
13 -23
-61 -11

output:

326

result:

ok single line: '326'

Test #17:

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

input:

10
-93 -97
-9 95
-35 94
-68 -16
-58 37
19 -99
-29 23
14 -60
-37 -48
-47 -99

output:

527

result:

ok single line: '527'

Test #18:

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

input:

10
18 -100
-24 24
-75 -89
-42 8
-80 62
93 25
-98 -19
-51 72
4 32
25 25

output:

546

result:

ok single line: '546'

Test #19:

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

input:

6
37 12
29 -27
-62 -50
11 -53
44 -15
-77 70

output:

376

result:

ok single line: '376'

Test #20:

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

input:

4
-6 -48
-64 -37
80 -5
3 64

output:

326

result:

ok single line: '326'

Test #21:

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

input:

8
-16 -72
-86 -53
90 -57
-59 28
56 47
91 13
-60 -21
-78 41

output:

513

result:

ok single line: '513'

Test #22:

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

input:

8
76 -67
-88 97
-20 29
-50 59
-39 48
27 -18
34 -25
56 -47

output:

333

result:

ok single line: '333'

Test #23:

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

input:

8
31 74
-53 -10
21 64
30 73
57 100
-52 -9
15 58
50 93

output:

225

result:

ok single line: '225'

Test #24:

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

input:

9
29 -3
96 64
2 -30
49 17
-32 -64
27 -5
55 23
21 -11
-66 -98

output:

329

result:

ok single line: '329'

Test #25:

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

input:

3
-15 -41
96 70
92 66

output:

227

result:

ok single line: '227'

Test #26:

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

input:

9
20 37
31 26
72 -15
-25 82
58 -1
76 -19
22 35
26 31
34 23

output:

207

result:

ok single line: '207'

Test #27:

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

input:

9
-13 -85
-98 0
-96 -2
-12 -86
-82 -16
-80 -18
-6 -92
-70 -28
-93 -5

output:

189

result:

ok single line: '189'

Test #28:

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

input:

8
-99 -79
-34 -14
68 88
-42 -22
-28 -8
6 26
4 24
14 34

output:

339

result:

ok single line: '339'

Test #29:

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

input:

6
-49 -72
-6 -29
61 38
92 69
-33 -56
-3 -26

output:

287

result:

ok single line: '287'

Test #30:

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

input:

8
26 -95
25 -94
-54 -15
-15 -54
22 -91
-39 -30
-50 -19
-25 -44

output:

165

result:

ok single line: '165'

Test #31:

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

input:

9
67 33
74 26
15 85
18 82
37 63
50 50
25 75
65 35
44 56

output:

123

result:

ok single line: '123'

Test #32:

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

input:

928
9500 1342
-7881 -5408
-6068 2272
764 -9877
-5181 -4671
2693 -1209
-3812 740
-7435 -7344
651 -3291
-4600 5063
8754 -328
1773 2138
7600 -74
-1670 -3442
6797 -4644
-2210 1409
7503 -6035
-958 9285
193 -5508
7249 -657
-5131 -8697
5096 -7891
-9423 2007
-3245 -3779
6887 -9459
-9269 647
6908 6326
3645 6...

output:

77873

result:

ok single line: '77873'

Test #33:

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

input:

169
6936 5081
5618 8088
-5765 -9632
5222 -8105
6474 -3280
-2624 9418
-3808 4388
-5907 3256
-2304 -1222
-2858 9116
3688 562
8021 -2717
9742 -2383
-2260 643
-7695 -3694
5694 809
9918 7229
7157 -8613
6628 9313
91 -4074
-5235 -1485
-7080 8703
7513 1894
-9582 -588
-2942 788
3007 -1539
-7216 -3973
3812 -6...

output:

70155

result:

ok single line: '70155'

Test #34:

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

input:

982
1816 -5967
-4260 -1809
-2231 -2712
844 -4972
-9502 -5807
4573 803
-165 -9542
5213 -4586
8204 -9338
-5987 5346
-2776 259
-8713 1220
5567 -9971
-9162 1136
-7821 3489
6955 1572
-3224 3616
-3771 -6699
8798 -5005
-4546 8265
4880 7595
8935 -7607
-7651 3702
-2959 -7771
4835 3799
4721 -5351
-3920 7617
9...

output:

76110

result:

ok single line: '76110'

Test #35:

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

input:

948
7264 8780
-8677 -2160
8517 -1833
1779 -8096
-372 -2433
9531 413
-2236 9743
9776 -2165
-2317 9848
-3255 7550
9080 -1872
1160 8144
360 -8478
8353 -4707
3244 7922
-1059 -2763
1873 -4106
6868 -34
5996 -8327
8969 722
-6024 1189
4137 589
3556 590
-1135 7561
6797 7066
3761 4542
6382 9066
3114 8561
9398...

output:

75323

result:

ok single line: '75323'

Test #36:

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

input:

730
-1743 -5203
-8233 913
-3735 1872
5071 2264
7527 2290
7827 4860
-5248 -9172
2768 7223
-4685 -2793
-1314 -3543
-331 -9886
-8989 4887
7985 8844
5984 -50
-9607 2860
-5311 5312
8426 1651
424 6430
8629 -2438
303 -309
-897 7570
8705 -3474
944 -8738
-6588 -1574
9113 3324
-5477 -5032
7654 -9986
-5007 710...

output:

74922

result:

ok single line: '74922'

Test #37:

score: 0
Accepted
time: 74ms
memory: 34360kb

input:

141317
-274942 -682201
-186052 -834038
-100601 61727
-944698 131823
635222 867300
-239410 817250
374969 -790867
-634764 -180132
170347 -815536
-517742 -6722
233434 -165940
-664181 523395
-705446 -753154
-793193 -360072
273024 -790792
581243 464110
-275845 -813563
725947 -118324
-797098 250331
884513...

output:

7974752

result:

ok single line: '7974752'

Test #38:

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

input:

3219
799461 -763629
-845801 -828705
436218 602504
64013 119629
-145168 23186
336602 -109589
602702 586542
131754 579855
-920365 -764639
179226 954008
-867415 959133
276457 158237
974550 316414
163430 264439
-647957 562192
-544042 -675651
-21138 -853886
-270398 525889
633758 731146
859843 789223
-553...

output:

7897260

result:

ok single line: '7897260'

Test #39:

score: 0
Accepted
time: 13ms
memory: 34244kb

input:

20296
872721 871788
928806 299409
352690 -755652
-332775 70799
-458562 664306
796842 -379164
-370289 557717
-435954 916731
-394675 -15900
417387 -920207
-493742 -157086
873833 -40616
79906 840493
538679 -450830
181308 395172
-880496 536539
-253127 153008
-759596 -968053
-144713 405014
-305183 -13728...

output:

7930553

result:

ok single line: '7930553'

Test #40:

score: 0
Accepted
time: 92ms
memory: 34324kb

input:

200000
-282804 959107
-747453 48772
-484768 -296154
482756 -763650
-435017 693599
-978517 640299
-121371 -683431
-77727 -710560
703571 885689
-335235 847996
-620488 891368
851990 -144059
56422 75285
853527 -382440
-274932 662212
654877 -205493
166985 -663763
-80386 -608151
749100 794472
685651 42769...

output:

7970085

result:

ok single line: '7970085'

Test #41:

score: 0
Accepted
time: 93ms
memory: 34288kb

input:

200000
-1000000 383683
1000000 905265
-474152 -1000000
787627 1000000
-1000000 -820522
-840177 1000000
1000000 -88481
-1000000 -170781
-172081 -1000000
-367521 -1000000
-766211 -1000000
-377722 -1000000
1000000 -58096
-1000000 -11022
-235995 -1000000
-1000000 -924069
396030 1000000
1000000 495411
49...

output:

7999928

result:

ok single line: '7999928'

Test #42:

score: 0
Accepted
time: 100ms
memory: 34344kb

input:

200000
-113124 681399
-646832 147691
105913 900436
-782103 12420
-254677 539846
-75306 719217
32514 827037
71770 866293
-404302 390221
-714475 80048
91667 886190
-728326 66197
-887910 -93387
-440470 354053
-301100 493423
-769098 25425
-803965 -9442
120598 915121
-74363 720160
124557 919080
-124198 6...

output:

2410937

result:

ok single line: '2410937'

Test #43:

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

input:

4
-1000000 -1000000
-1000000 1000000
1000000 -1000000
1000000 1000000

output:

8000004

result:

ok single line: '8000004'