QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123568 | #6639. Disk Tree | installb | WA | 2ms | 9648kb | C++14 | 3.3kb | 2023-07-12 21:24:02 | 2023-07-12 21:24:04 |
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];
struct node{
int x,yl,yr;
bool operator < (const node &nd)const{
if(x == nd.x) return yl < nd.yl;
return x < nd.x;
}
};
node lis[N << 2]; int lsc = 0;
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]});
}
G.clear();
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{
lis[++ lsc] = {x[u] - r[u],min(y[id],y[u]),max(y[id],y[u])};
// ans.push_back({x[u] - r[u],y[id],x[u] - r[u],y[u]});
}
if(i > 1 && x[s[i].id] - r[s[i].id] != x[s[i - 1].id] - r[s[i - 1].id]){
for(auto pi : G) st.insert(pi);
G.clear();
}
G.push_back({y[u],u});
mxr = max(mxr,{x[u] + r[u],u});
}
sort(lis + 1,lis + 1 + lsc);
vector <int> H;
for(int my = -1,i = 1;i <= lsc;i ++){
H.push_back(lis[i].yl); H.push_back(lis[i].yr);
my = max(my,lis[i].yr);
if(i == lsc || lis[i + 1].x != lis[i].x || lis[i + 1].yl > my){
sort(H.begin(),H.end());
H.erase(unique(H.begin(),H.end()),H.end());
for(int j = 1;j < H.size();j ++) ans.push_back({lis[i].x,H[j - 1],lis[i].x,H[j]});
my = 0; H.clear();
}
}
if(ans.size() != n - 1) cout << ans.size() << endl;
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: 9544kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 0 0 5 4 0 4 10
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 2ms
memory: 9556kb
input:
2 1 1 1 3 3 1
output:
YES 2 1 2 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 9648kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 1 0 1 10 2 10 2 20 19 0 19 10 19 10 19 20
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 2ms
memory: 9608kb
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 27 24 18 55 58 68 88 95 108 95 95 81 7 8 7 24 7 24 7 82 24 0 24 24 27 29 27 55 35 55 35 88 38 55 38 68
result:
ok answer = 1
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 9560kb
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 7 952 20 607 20 663 39 843 39 952 60 703 60 773 63 850 63 952 64 226 64 366 75 790 75 850 81 208 81 226 100 115 100 366 111 603 111 703 120 512 120 703 129 156 129 366 134 241 134 366 176 100 176 366 179 703 179 934 198 323 198 512...
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