QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123552 | #6639. Disk Tree | installb | WA | 2ms | 9584kb | C++14 | 2.3kb | 2023-07-12 20:40:06 | 2023-07-12 20:40:08 |
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;
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;
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;
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[id],y[id],x[u],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: 2ms
memory: 7588kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 0 0 5 1 0 10 10
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 7560kb
input:
2 1 1 1 3 3 1
output:
YES 1 1 3 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 2ms
memory: 7508kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 10 10 2 0 10 10 3 20 10 10 20 0 10 10 20 20
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 7604kb
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 0 8 17 24 17 24 17 82 17 82 28 55 17 24 34 0 28 55 29 29 28 55 45 88 45 88 48 68 58 68 88 95 98 95 99 81
result:
ok answer = 1
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 9584kb
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 32 773 67 952 29 663 35 607 67 952 51 843 32 773 160 703 67 952 116 850 92 366 76 226 116 850 81 790 76 226 95 208 95 208 133 115 160 703 119 603 119 603 204 512 92 366 137 156 92 366 195 241 195 241 205 100 160 703 235 934 204 512 223 3...
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