QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234788 | #2295. Dyson Circle | CodeZhazgysh | AC ✓ | 100ms | 34428kb | C++14 | 3.1kb | 2023-11-01 22:27:41 | 2023-11-01 22:27:41 |
Judging History
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'