QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234716#3163. BomasPhantom Threshold (Jiachen Tang, Changdong Li, Weinuo Li)#AC ✓424ms82284kbC++202.3kb2023-11-01 21:15:372023-11-01 21:15:39

Judging History

This is the latest submission verdict.

  • [2023-11-01 21:15:39]
  • Judged
  • Verdict: AC
  • Time: 424ms
  • Memory: 82284kb
  • [2023-11-01 21:15:37]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const long double eps=1e-9;
int curx;
struct circ
{
	int x,y,r,id,ty;
	long double eval()const
	{
		return y+ty*sqrt(max(0.0L,(1.0L*r*r-1.0L*(curx-x)*(curx-x))));
	}
	bool operator<(const circ &c)const
	{
		auto w=eval(),w2=c.eval();
		if(fabs(w-w2)<eps)return ty<c.ty;
		else return w<w2;
	}
};
int main()
{
	ios_base::sync_with_stdio(false);
	int n,q;
	cin>>n>>q;
	vector<tuple<int,int,int,int,int,circ>> events;
	for(int i=1;i<=n;i++)
	{
		int x,y,r;
		cin>>x>>y>>r;
		events.emplace_back(x-r,1,-y,1,i,(circ){x,y,r,i,-1});
		events.emplace_back(x+r,-1,-y,1,i,(circ){x,y,r,i,-1});
		events.emplace_back(x-r,1,-y,-1,i,(circ){x,y,r,i,1});
		events.emplace_back(x+r,-1,-y,-1,i,(circ){x,y,r,i,1});
	}
	for(int i=1;i<=q;i++)
	{
		int x,y,r;
		cin>>x>>y>>r;
		events.emplace_back(x-r,1,-y,1,i+n,(circ){x,y,r,i+n,-1});
		events.emplace_back(x+r,-1,-y,1,i+n,(circ){x,y,r,i+n,-1});
		events.emplace_back(x-r,1,-y,-1,i+n,(circ){x,y,r,i+n,1});
		events.emplace_back(x+r,-1,-y,-1,i+n,(circ){x,y,r,i+n,1});
	}
	vector<vector<int>> G(n+q+5);
	vector<int> pa(n+q+5);
	sort(events.begin(),events.end());
	set<circ> s;
	for(const auto &[pos,ty,ypos,ud,id,c]:events)
	{
		curx=pos;
//		if(ty==1)cerr<<"add circle ";
//		else cerr<<"del circle ";
//		cerr<<pos<<' '<<ypos<<' '<<ud<<' '<<id<<' '<<c.x<<' '<<c.y<<' '<<c.r<<' '<<c.ty<<endl;
		if(ty==1 and c.ty==1)
		{
			auto it=s.upper_bound(c);
			if(it==s.end())pa[id]=0;
			else
			{
				if(it->ty==-1)pa[id]=pa[it->id];
				else pa[id]=it->id;
			}
		}
		if(ty==1)s.insert(c);
		else s.erase(c);
	}
	for(int i=1;i<=n+q;i++)
	{
//		cerr<<"pa "<<i<<' '<<pa[i]<<endl;
		G[pa[i]].push_back(i);
	}
	vector<vector<int>> dp(n+q+5,vector<int>(2));
	vector<int> ans(q+5);
	function<void(int)> dfs=[&](int u)
	{
		for(auto v:G[u])
		{
			dfs(v);
		}
		dp[u][1]=1;
		for(auto v:G[u])
		{
			dp[u][0]+=dp[v][1];
			dp[u][1]+=dp[v][0];
		}
		dp[u][1]=max(dp[u][0],dp[u][1]);
		if(u>n)
		{
			ans[u-n]=dp[u][1];
			dp[u][0]=dp[u][1]=0;
			for(auto v:G[u])
			{
				dp[u][0]+=dp[v][0];
				dp[u][1]+=dp[v][1];
			}
		}
	};
	for(int i=1;i<=n+q;i++)
	{
		if(not pa[i])
		{
			dfs(i);
		}
	}
	for(int i=1;i<=q;i++)
	{
		cout<<ans[i]<<"\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5
0 0 100
0 50 20
0 -50 20
0 0 80
0 0 2
500 0 2
0 50 25
0 0 150

output:

2
1
1
1
3

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 424ms
memory: 82284kb

input:

100000 100000
0 0 177461
0 0 1212
0 0 106548
0 0 93559
0 0 155649
0 0 8291
0 0 183489
0 0 29821
0 0 191678
0 0 71901
0 0 33471
0 0 132700
0 0 145730
0 0 76077
0 0 60942
0 0 128623
0 0 40935
0 0 31129
0 0 90101
0 0 35338
0 0 48909
0 0 176056
0 0 88015
0 0 162994
0 0 89426
0 0 157047
0 0 149106
0 0 66...

output:

13037
19135
13258
12786
36495
41010
10043
10595
1790
42734
19510
7466
12734
399
22483
65
44682
5971
24586
5683
6185
45000
38645
36401
2060
6820
19429
20203
15172
1535
961
22850
39203
735
32462
7427
48457
30027
43505
20521
45017
21763
31570
38556
36905
4518
34405
11379
1423
46918
18962
28138
39470
40...

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 164ms
memory: 35540kb

input:

100000 1000
0 -585740 7
0 -53180 9
0 571380 1
0 228460 1
0 315240 5
0 -288560 3
0 -187500 2
0 -695880 2
0 -624540 2
0 -443260 3
0 -192120 9
0 978300 2
0 -564880 3
0 285580 2
0 -696220 2
0 954360 4
0 -19820 9
0 -123320 1
0 931400 6
0 149160 9
0 56380 9
0 39460 7
0 -360660 5
0 23600 7
0 222900 6
0 756...

output:

29
61
31
33
41
33
51
19
59
9
33
47
41
15
35
59
45
27
21
37
33
53
27
3
1
9
3
21
49
39
1
27
43
7
41
5
1
13
3
7
47
35
47
9
41
33
11
15
37
35
17
5
23
23
49
25
17
15
49
15
53
33
47
1
41
7
17
33
53
7
17
43
17
61
27
31
31
47
53
15
5
39
7
23
35
45
59
15
49
13
47
29
15
37
1
25
23
61
7
59
15
35
47
57
51
45
19...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 273ms
memory: 51752kb

input:

100000 50000
7068750 7131250 2
-7131250 7068750 3
7131250 -7068750 1
-7068750 -7131250 1
7068755 7131245 2
-7131245 7068755 3
7131245 -7068755 1
-7068755 -7131245 3
7068760 7131240 1
-7131240 7068760 1
7131240 -7068760 1
-7068760 -7131240 1
7068765 7131235 3
-7131235 7068765 3
7131235 -7068765 3
-70...

output:

19177
12510
14311
19825
16433
7356
3708
4170
19481
13152
14357
15239
5840
5941
9243
11317
14464
19210
7867
5479
11014
21098
1960
14425
994
7411
14615
2900
7098
19671
4817
2958
11286
20903
3323
3847
22084
20399
14357
13564
10673
18188
15420
11072
20096
12840
16900
13163
8387
9690
9810
3926
76
11731
1...

result:

ok 50000 lines

Test #5:

score: 0
Accepted
time: 172ms
memory: 53720kb

input:

100000 100000
0 0 1
3 0 1
6 0 1
9 0 1
12 0 1
15 0 1
18 0 1
21 0 1
24 0 1
27 0 1
30 0 1
33 0 1
36 0 1
39 0 1
42 0 1
45 0 1
48 0 1
51 0 1
54 0 1
57 0 1
60 0 1
63 0 1
66 0 1
69 0 1
72 0 1
75 0 1
78 0 1
81 0 1
84 0 1
87 0 1
90 0 1
93 0 1
96 0 1
99 0 1
102 0 1
105 0 1
108 0 1
111 0 1
114 0 1
117 0 1
120 ...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 273ms
memory: 53452kb

input:

100000 100000
1300000 -150000 1418
1300000 1740000 844
1300000 1920000 3257
1300000 -1920000 193
1300000 -100000 484
1300000 -440000 2288
1300000 1180000 527
1300000 -1190000 2119
1300000 -1590000 42
1300000 1400000 2458
1300000 1160000 1991
1300000 1070000 2112
1300000 -1350000 1723
1300000 -390000...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #7:

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

input:

4 6
0 13 11
0 34 8
0 12 2
0 30 2
0 52 2
0 18 2
0 29 29
0 6 2
0 46 2
0 36 2

output:

1
1
3
1
1
1

result:

ok 6 lines

Test #8:

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

input:

39 61
0 299 299
0 382 56
0 258 8
0 453 11
0 8 2
0 341 11
0 104 2
0 29 17
0 399 5
0 495 11
0 446 2
0 50 2
0 22 8
0 202 2
0 529 5
0 468 2
0 544 2
0 550 2
0 408 2
0 559 5
0 491 5
0 284 2
0 168 2
0 59 5
0 571 5
0 110 2
0 254 2
0 224 2
0 300 2
0 580 2
0 334 2
0 306 2
0 140 2
0 71 5
0 80 2
0 116 2
0 34 2
...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
12
7
7
3
2
2
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 61 lines

Test #9:

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

input:

481 519
0 2999 2999
0 2230 2228
0 552 548
0 1434 332
0 143 137
0 1172 68
0 73 65
0 3300 98
0 5191 65
0 4791 167
0 2795 101
0 3675 41
0 421 137
0 5380 50
0 193 53
0 3260 56
0 2912 14
0 5437 5
0 390 104
0 5467 23
0 577 17
0 1277 35
0 2719 23
0 3930 62
0 513 17
0 2951 23
0 4077 83
0 5650 38
0 1787 17
0...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
30
44
24
37
32
10
12
6
6
9
10
9
2
2
6
7
6
7
7
2
5
3
5
2
9
3
1
2
2
3
7
5
3
2
1
4
1
5
7
2
5
1
1
2
2
3
3
1
2
3
2
6
2
2
1
2
1
1
1
3
1
2
3
1
2
1
2
2
2
2
1
1
1
1
1
1
1
3
1
2
1
3
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
2
1
2
5
1
1
1
1
1
1
1
...

result:

ok 519 lines

Test #10:

score: 0
Accepted
time: 17ms
memory: 7152kb

input:

4970 5030
0 15103 7883
0 25957 2969
0 11478 4256
0 37837 1109
0 42766 1784
0 23280 290
0 17262 1526
0 19332 542
0 16178 440
0 29136 206
0 25206 524
0 51478 260
0 47898 1010
0 30075 731
0 1050 230
0 2142 860
0 47375 485
0 16937 317
0 54730 122
0 45582 1028
0 23858 284
0 3156 152
0 17636 380
0 13856 8...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3749
434
241
245
132
91
104
52
148
129
280
76
108
82
96
60
46
22
77
50
46
62
41
19
49
25
44
14
9
10
10
30
25
17
37
31
35
7
10
22
25
12
35
33
19
23
16
59
12
18
7
20
16
18
4
16
22
16...

result:

ok 5030 lines

Test #11:

score: 0
Accepted
time: 171ms
memory: 35632kb

input:

49988 50012
0 299999 299999
0 109750 109748
0 437818 24602
0 40308 40304
0 93183 12569
0 316809 19721
0 20795 20789
0 348633 12101
0 46010 4424
0 526771 20801
0 241596 5498
0 2302 2294
0 255099 8003
0 338576 2042
0 422904 9686
0 167442 3350
0 266847 3743
0 317681 7685
0 521922 8708
0 372276 4694
0 5...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4839
4426
2871
1531
1226
993
1646
1423
614
812
292
660
457
723
232
474
682
1262
683
521
536
396
558
203
407
501
447
209
368
142
237
145
237
265
489
204
163
252
122
169
77
51
69
96
143
286
54
100
178
69
189
150
122
100
276
76
144
365
47
160
183
136
93
1...

result:

ok 50012 lines

Test #12:

score: 0
Accepted
time: 144ms
memory: 53452kb

input:

100000 100000
-9999359 -9999999 1
-9998719 -9999999 1
-9998079 -9999999 1
-9997439 -9999999 1
-9996799 -9999999 1
-9996159 -9999999 1
-9995519 -9999999 1
-9994879 -9999999 1
-9994239 -9999999 1
-9993599 -9999999 1
-9992959 -9999999 1
-9992319 -9999999 1
-9991679 -9999999 1
-9991039 -9999999 1
-99903...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines