QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107700#5385. Goblin Garden GuardsPetroTarnavskyi#AC ✓350ms350836kbC++171.1kb2023-05-22 15:44:522023-05-22 15:44:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-22 15:44:53]
  • 评测
  • 测评结果:AC
  • 用时:350ms
  • 内存:350836kb
  • [2023-05-22 15:44:52]
  • 提交

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'