QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123561 | #6639. Disk Tree | installb | WA | 2ms | 11648kb | C++14 | 3.0kb | 2023-07-12 21:13:22 | 2023-07-12 21:13:25 |
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]});
}
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]});
}
st.insert({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){
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: 1ms
memory: 9560kb
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: 9548kb
input:
2 1 1 1 3 3 1
output:
YES 2 1 2 3
result:
ok answer = 1
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 11648kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
5 YES 1 0 1 10 2 10 2 20 19 0 19 10 19 10 19 10 19 10 19 20
result:
wrong answer Token parameter [name=YES or NO] equals to "5", doesn't correspond to pattern "[A-Za-z]+"