QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107700 | #5385. Goblin Garden Guards | PetroTarnavskyi# | AC ✓ | 350ms | 350836kb | C++17 | 1.1kb | 2023-05-22 15:44:52 | 2023-05-22 15:44:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int N = 10447;
int a[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<VI> v(N);
FOR(i, 0, n)
{
int x, y;
cin >> x >> y;
v[x].PB(y);
}
FOR (i, 0, N) sort(ALL(v[i]));
int m;
cin >> m;
FOR (i, 0, m)
{
int x, y, r;
cin >> x >> y >> r;
FOR (dx, -r, r + 1)
{
if (x + dx < 0) continue;
int d = sqrt(r * r - dx * dx);
a[x + dx][max(0, y - d)]++;
a[x + dx][y + d + 1]--;
}
}
int ans = 0;
FOR(i, 0, N)
{
int cnt = 0;
int k = 0;
FOR(j, 0, N)
{
cnt += a[i][j];
int c = 0;
while (k < SZ(v[i]) && v[i][k] == j)
{
c++;
k++;
}
if (cnt == 0)
ans += c;
}
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 5532kb
input:
5 0 0 100 0 0 100 100 100 50 50 1 0 0 50
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 4ms
memory: 9716kb
input:
10 13 49 55 85 93 67 78 30 43 69 33 73 70 31 70 3 90 51 18 62 5 23 82 96 78 12 66 97 24 16 12 97 83 55 97 13
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 9676kb
input:
10 23 73 22 32 36 98 32 26 36 53 62 76 55 31 72 60 58 41 62 38 5 96 92 55 99 82 63 63 82 2 26 4 73 10 83 22
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9620kb
input:
10 49 59 6 100 76 4 97 6 69 33 74 45 22 17 68 21 69 24 43 68 5 62 10 44 89 51 69 29 71 9 76 45 93 93 22 10
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 4ms
memory: 48812kb
input:
1000 747 966 416 548 315 882 117 681 281 686 455 328 61 407 78 524 163 777 882 940 405 849 588 521 3 33 938 621 790 148 191 962 76 678 803 557 594 797 355 744 769 726 172 969 126 426 294 710 791 501 305 972 855 567 435 574 133 497 762 765 380 183 184 710 366 158 281 709 550 695 443 114 490 951 350 3...
output:
11
result:
ok single line: '11'
Test #6:
score: 0
Accepted
time: 4ms
memory: 46724kb
input:
1000 944 686 158 832 830 715 825 422 684 278 439 357 835 43 451 239 12 891 193 934 439 492 941 391 1 861 514 726 749 279 960 777 397 675 212 988 647 455 850 52 504 508 692 426 668 466 640 255 359 849 329 778 303 542 59 153 44 752 67 785 840 193 959 420 888 636 836 719 260 930 471 89 498 387 371 421 ...
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 5ms
memory: 48648kb
input:
1000 549 340 949 478 60 731 879 508 551 508 249 856 66 165 110 340 184 986 463 589 574 891 717 618 409 705 461 14 460 505 175 276 421 34 697 407 599 925 69 960 809 805 415 937 279 92 991 331 224 243 129 234 300 858 975 906 409 208 88 618 558 371 199 471 76 345 168 967 552 743 412 216 784 416 520 823...
output:
14
result:
ok single line: '14'
Test #8:
score: 0
Accepted
time: 350ms
memory: 350836kb
input:
100000 409 6634 9449 147 1470 849 6318 3524 5520 6083 9470 3654 6593 7593 5940 2178 431 6018 9365 9214 7642 1035 5625 8881 9246 9373 3686 591 8987 3816 9407 5447 8205 2547 1514 3786 3771 9010 1965 3802 4856 5457 4023 1006 8187 4363 332 167 2946 837 6965 6280 5853 2781 1524 745 2912 5955 3371 4754 83...
output:
90370
result:
ok single line: '90370'
Test #9:
score: 0
Accepted
time: 24ms
memory: 16392kb
input:
100000 1018 8746 1054 6216 1035 4927 1089 9893 1029 372 1068 9509 1010 5830 1041 4377 1079 1935 1040 788 1097 1531 1040 7960 1029 5047 1035 4708 1064 2713 1076 7278 1005 3678 1030 4312 1056 2660 1042 459 1096 2775 1098 2224 1070 3811 1009 6759 1024 7776 1031 5084 1086 7481 1017 1380 1031 4949 1001 9...
output:
106
result:
ok single line: '106'
Test #10:
score: 0
Accepted
time: 64ms
memory: 258616kb
input:
100000 7204 1062 1491 1065 5197 1089 5851 1079 2369 1027 7624 1007 387 1011 4249 1041 6208 1032 1026 1075 8149 1053 928 1011 3479 1077 8728 1073 9309 1006 6295 1090 3741 1037 9262 1011 5926 1051 211 1043 7231 1044 9973 1055 940 1003 7340 1017 7828 1014 3754 1039 3482 1055 3415 1059 3 1010 3496 1076 ...
output:
71
result:
ok single line: '71'
Test #11:
score: 0
Accepted
time: 16ms
memory: 16252kb
input:
100000 4741 4744 4732 4732 4732 4746 4753 4769 4773 4758 4715 4796 4801 4733 4781 4724 4793 4803 4811 4774 4739 4722 4789 4807 4785 4800 4797 4777 4782 4796 4726 4718 4754 4781 4729 4740 4764 4730 4810 4730 4761 4726 4717 4752 4735 4800 4804 4788 4755 4777 4804 4791 4733 4769 4724 4736 4778 4806 477...
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 20ms
memory: 14188kb
input:
100000 4783 4764 4761 4756 4724 4776 4747 4754 4807 4731 4748 4726 4734 4791 4739 4793 4752 4787 4742 4737 4777 4803 4770 4726 4798 4773 4780 4735 4739 4718 4749 4797 4761 4781 4741 4743 4752 4761 4776 4780 4725 4755 4795 4765 4775 4732 4749 4766 4803 4722 4808 4767 4716 4717 4759 4753 4791 4714 471...
output:
21860
result:
ok single line: '21860'
Test #13:
score: 0
Accepted
time: 14ms
memory: 6020kb
input:
100000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 1009 1000 100...
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 18ms
memory: 5988kb
input:
100000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 1010 1000 101...
output:
47208
result:
ok single line: '47208'
Test #15:
score: 0
Accepted
time: 11ms
memory: 8040kb
input:
100000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 1011 1000 101...
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 15ms
memory: 8080kb
input:
100000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 1020 1000 102...
output:
58867
result:
ok single line: '58867'
Test #17:
score: 0
Accepted
time: 29ms
memory: 14388kb
input:
100000 2113 3840 2111 4354 2034 8313 2140 370 2104 9996 2106 1906 2068 2783 2110 8986 2086 3294 2052 88 2059 1283 2023 5085 2119 9371 2025 3124 2055 2166 2036 782 2072 1643 2188 5160 2128 4610 2148 7577 2072 1399 2117 1146 2045 2101 2040 9319 2090 6909 2061 3524 2157 3398 2162 263 2068 9941 2010 309...
output:
986
result:
ok single line: '986'
Test #18:
score: 0
Accepted
time: 94ms
memory: 260364kb
input:
100000 9206 2116 4451 2040 7035 2110 8932 2052 6288 2074 8970 2059 7032 2178 9525 2159 8926 2009 3204 2050 402 2075 10000 2105 6399 2004 1479 2165 3160 2063 6226 2044 1609 2024 3384 2158 2476 2098 5402 2120 2976 2083 7741 2043 3928 2096 5029 2152 3406 2131 9445 2145 8454 2044 1130 2020 9441 2029 234...
output:
995
result:
ok single line: '995'
Test #19:
score: 0
Accepted
time: 26ms
memory: 22360kb
input:
100000 4044 4339 4184 4292 4142 4391 4082 4446 4082 4088 4500 4282 4163 4167 4032 4421 4351 4047 4202 4408 4452 4092 4136 4073 4319 4496 4463 4300 4030 4494 4009 4282 4071 4219 4294 4319 4249 4461 4339 4187 4161 4021 4453 4389 4405 4384 4493 4479 4447 4473 4076 4053 4314 4463 4396 4230 4040 4444 405...
output:
41158
result:
ok single line: '41158'
Test #20:
score: 0
Accepted
time: 31ms
memory: 26460kb
input:
100000 4424 4289 4174 4089 4422 4410 4356 4258 4227 4473 4073 4028 4431 4483 4250 4390 4014 4323 4483 4007 4166 4167 4009 4314 4044 4407 4364 4099 4427 4033 4129 4202 4189 4060 4447 4313 4001 4120 4214 4035 4033 4369 4396 4490 4437 4178 4078 4222 4414 4450 4440 4323 4135 4025 4276 4392 4374 4026 445...
output:
98064
result:
ok single line: '98064'
Test #21:
score: 0
Accepted
time: 27ms
memory: 26468kb
input:
100000 4341 4103 4162 4480 4500 4253 4097 4324 4286 4432 4321 4479 4486 4487 4022 4019 4118 4349 4036 4020 4363 4177 4025 4209 4347 4404 4263 4011 4076 4286 4220 4488 4216 4431 4344 4427 4403 4140 4167 4416 4488 4472 4223 4153 4022 4255 4228 4073 4182 4231 4196 4159 4462 4086 4314 4344 4246 4207 401...
output:
28531
result:
ok single line: '28531'
Test #22:
score: 0
Accepted
time: 17ms
memory: 6132kb
input:
100000 4001 4115 4003 9750 4001 3244 4005 4481 4010 9963 4008 6628 4010 2109 4001 6223 4006 2627 4007 180 4007 8047 4007 8497 4000 97 4008 2172 4001 1626 4008 6399 4007 4057 4005 3772 4004 8002 4000 9215 4005 9446 4007 244 4007 1752 4002 1240 4003 1189 4006 6625 4007 1905 4010 3987 4004 2939 4005 34...
output:
97086
result:
ok single line: '97086'
Test #23:
score: 0
Accepted
time: 146ms
memory: 26716kb
input:
100000 9022 4001 7780 4002 6010 4001 1859 4004 3870 4010 3706 4003 2775 4004 596 4007 5598 4006 9974 4006 9779 4004 261 4000 8204 4008 9394 4000 6442 4010 4561 4008 2024 4009 9834 4003 6524 4002 7752 4008 8729 4008 145 4006 4406 4001 9166 4006 5149 4006 1059 4010 4599 4007 9748 4006 9009 4005 7070 4...
output:
97100
result:
ok single line: '97100'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
100 1 18 19 8 1 6 5 22 17 4 11 3 14 1 19 7 0 15 2 21 19 19 11 1 12 2 16 23 5 3 13 3 4 2 11 2 17 21 9 1 15 3 12 24 20 15 5 23 7 3 4 23 13 24 14 3 17 5 2 20 3 4 15 2 6 3 8 24 8 23 8 1 6 2 16 22 15 4 20 14 15 22 10 24 15 23 7 24 4 4 10 25 16 4 9 2 2 4 11 24 9 24 18 5 13 23 10 2 20 12 6 1 1 7 14 2 5 4 1...
output:
42
result:
ok single line: '42'
Test #25:
score: 0
Accepted
time: 30ms
memory: 16124kb
input:
100000 69 332 76 20 83 1016 86 785 3 855 95 807 44 135 12 745 39 200 29 740 11 801 9 1059 25 1001 10 94 83 764 96 1081 55 864 82 829 86 326 28 117 94 748 64 324 23 1069 55 1010 5 881 73 717 90 501 90 77 9 234 95 788 51 813 83 64 14 397 19 1095 22 227 71 766 22 366 50 807 3 450 25 1026 83 228 13 152 ...
output:
85314
result:
ok single line: '85314'
Test #26:
score: 0
Accepted
time: 29ms
memory: 16372kb
input:
100000 305 69 333 23 471 11 656 4 366 28 718 83 44 86 132 49 675 46 764 93 957 41 669 63 180 73 847 9 144 82 423 5 869 56 796 91 1098 19 905 84 740 41 945 6 307 35 149 80 803 92 1021 71 808 78 453 37 305 79 802 45 859 70 502 26 931 28 18 40 1135 57 785 14 214 58 770 27 814 16 382 70 382 88 853 63 91...
output:
85314
result:
ok single line: '85314'
Test #27:
score: 0
Accepted
time: 27ms
memory: 18360kb
input:
100000 928 97 394 49 101 20 395 40 660 92 492 35 333 19 188 56 792 66 755 88 887 61 425 51 245 74 148 42 106 63 660 59 8 5 296 49 821 70 366 89 822 14 230 22 857 43 837 3 636 63 212 32 229 64 703 63 883 38 915 46 812 45 504 37 222 64 102 95 173 61 291 21 260 26 5 85 911 80 726 84 322 8 859 10 921 83...
output:
100000
result:
ok single line: '100000'
Test #28:
score: 0
Accepted
time: 31ms
memory: 16616kb
input:
100000 50 35 120 734 78 94 42 594 35 779 22 633 40 862 19 107 61 813 56 737 24 737 121 718 41 651 55 252 71 856 118 364 112 356 29 648 24 609 17 35 75 173 23 715 64 264 59 709 9 513 66 319 3 122 62 635 136 155 29 214 128 630 134 654 11 180 71 556 107 328 13 160 128 143 129 221 63 876 62 142 4 270 13...
output:
78734
result:
ok single line: '78734'
Test #29:
score: 0
Accepted
time: 35ms
memory: 18652kb
input:
100000 90 82 118 37 304 138 694 28 148 15 189 13 870 108 837 121 854 80 116 140 195 80 225 48 819 88 735 67 617 31 714 104 45 117 618 35 127 4 792 15 552 40 327 46 562 84 795 102 37 29 197 105 76 22 865 66 701 79 344 108 124 83 669 94 206 113 344 78 627 101 835 84 181 134 795 18 165 77 652 15 554 41...
output:
78734
result:
ok single line: '78734'
Test #30:
score: 0
Accepted
time: 40ms
memory: 22504kb
input:
100000 351 386 453 340 449 178 227 196 498 271 377 471 294 461 265 453 206 353 434 319 262 130 156 430 311 421 199 234 172 230 145 301 268 420 408 424 425 189 254 127 367 467 387 168 267 176 495 253 482 280 405 416 241 407 381 128 430 256 200 348 338 456 119 269 389 394 345 202 480 366 330 475 364 4...
output:
30030
result:
ok single line: '30030'
Test #31:
score: 0
Accepted
time: 27ms
memory: 10056kb
input:
100000 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50 100 50...
output:
100000
result:
ok single line: '100000'