QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234716 | #3163. Bomas | Phantom Threshold (Jiachen Tang, Changdong Li, Weinuo Li)# | AC ✓ | 424ms | 82284kb | C++20 | 2.3kb | 2023-11-01 21:15:37 | 2023-11-01 21:15:39 |
Judging History
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