QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123556 | #6639. Disk Tree | installb | WA | 2ms | 9624kb | C++14 | 2.3kb | 2023-07-12 20:51:00 | 2023-07-12 20:51:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400005;
struct interval{
int l,r,pos,id;
bool operator < (const interval &o)const{
if(l == o.l) return pos < o.pos;
return l < o.l;
}
}s[N];
set <pair <int,int> > st;
vector <tuple <int,int,int,int> > ans;
int n,x[N],y[N],r[N];
void solve(){
cin >> n;
for(int i = 1;i <= n;i ++){
cin >> x[i] >> y[i] >> r[i];
s[i] = {x[i] - r[i],x[i] + r[i],y[i],i};
}
sort(s + 1,s + 1 + n);
// x has to be >= 0, so connect all possible circles with x = 0 first
int pos = 0;
for(int i = 1;i <= n;i ++){
if(x[s[i].id] - r[s[i].id] <= 0) pos = i;
else break;
}
vector <pair <int,int> > G;
for(int i = 1;i <= pos;i ++){
G.push_back({y[s[i].id],s[i].id});
st.insert({y[s[i].id],s[i].id});
}
sort(G.begin(),G.end());
for(int i = 1;i < G.size();i ++){
int u = G[i - 1].second,v = G[i].second;
ans.push_back({0,y[u],0,y[v]});
}
pair <int,int> mxr = {-1,-1};
for(int i = 1;i <= pos;i ++) mxr = max(mxr,{x[s[i].id] + r[s[i].id],s[i].id});
for(int i = pos + 1;i <= n;i ++){
int u = s[i].id,id = -1,flg = 0;
while(st.size()){
auto it = st.lower_bound({y[u],-1});
if(it == st.end()) break;
int v = it->second;
if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
else{
id = v; flg = 0;
break;
}
}
if(id == -1){
while(st.size()){
auto it = -- st.lower_bound({y[u],-1});
int v = it->second;
if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
else{
id = v; flg = 1;
break;
}
}
}
if(id == -1 && i > 1) ans.push_back({mxr.first,y[mxr.second],x[u] - r[u],y[u]});
else ans.push_back({x[u] - r[u],y[id],x[u] - r[u] + flg,y[u]});
st.insert({y[u],u});
mxr = max(mxr,{x[u] + r[u],u});
}
cout << "YES\n";
for(auto [a,b,c,d] : ans) cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
int main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7540kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 0 0 5 4 0 5 10
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 2ms
memory: 7452kb
input:
2 1 1 1 3 3 1
output:
YES 2 1 3 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 1ms
memory: 7568kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 1 10 1 0 2 10 3 20 19 10 19 0 19 10 20 20
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 2ms
memory: 7508kb
input:
10 29 29 2 28 55 10 99 81 4 17 82 10 45 88 10 48 68 10 0 8 10 98 95 10 34 0 10 17 24 10
output:
YES 7 8 8 24 7 24 8 82 18 82 18 55 24 24 24 0 27 55 27 29 35 55 36 88 38 88 38 68 58 68 88 95 95 95 95 81
result:
ok answer = 1
Test #5:
score: 0
Accepted
time: 2ms
memory: 9624kb
input:
100 490 783 12 666 460 55 561 245 6 223 323 25 3 520 77 225 161 24 514 190 16 997 914 100 412 265 100 374 610 36 296 854 39 601 901 2 307 21 100 390 422 24 940 414 32 332 438 35 553 992 100 235 775 3 656 901 37 770 417 22 649 305 100 448 84 3 375 939 77 910 847 9 776 357 37 743 97 100 371 502 39 508...
output:
YES 0 13 0 179 0 179 0 366 0 366 0 520 0 520 0 663 0 663 0 773 7 773 8 952 20 663 20 607 39 952 39 843 60 773 60 703 63 952 63 850 64 366 64 226 75 850 75 790 81 226 81 208 100 208 100 115 111 703 111 603 120 603 120 512 129 366 129 156 134 366 134 241 176 241 176 100 179 703 180 934 198 512 198 323...
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 1ms
memory: 7516kb
input:
200 2948 9798 687 3897 647 35 3918 587 28 1262 2717 206 1315 9524 20 2381 305 1000 4344 6858 20 6234 8949 53 5168 4772 85 5044 6109 158 72 7670 132 7300 1213 837 5427 2263 1000 1785 3009 276 6136 1421 43 1629 5620 29 6445 9489 242 8443 3141 1000 4118 4307 63 1874 5238 291 1964 5785 73 7794 3934 18 3...
output:
YES 0 1148 0 2852 0 2852 0 4653 0 4653 0 6162 0 6162 0 7670 55 7670 56 7903 87 7903 88 9469 113 9469 113 8944 139 4653 139 3990 178 7670 178 7484 265 1148 265 51 289 7484 289 6779 305 6162 305 5282 349 9469 349 9349 374 9469 375 9493 413 2852 413 1890 432 6162 432 5542 440 8944 440 8185 555 2852 555...
result:
ok answer = 1
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 7596kb
input:
300 42942 37079 222 49441 21821 1695 61023 31153 561 86630 26307 352 36940 78253 213 7841 81086 626 47425 22290 374 17694 68695 648 38259 64794 998 43599 46942 9662 9204 2816 1965 38652 83568 4057 4046 29001 1034 72591 63214 587 75984 64859 1112 70005 72177 576 34522 52126 652 56627 48785 1747 78820...
output:
YES 0 16007 0 24419 0 24419 0 39900 0 39900 0 58648 0 58648 0 69461 0 69461 0 79893 0 79893 0 99921 110 16007 110 7853 414 99921 414 91204 548 91204 548 90680 1003 99921 1003 92828 1725 39900 1725 32550 2213 58648 2213 46829 3012 32550 3012 29001 3149 58648 3149 47905 3325 79893 3325 73213 3840 2441...
result:
wrong answer Two line segments intersect, and it's not only the endpoints that intersect or line segments intersects/touches more than 2 disks