QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123572 | #6639. Disk Tree | installb | WA | 2ms | 19160kb | C++14 | 4.2kb | 2023-07-12 21:48:58 | 2023-07-12 21:48:59 |
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,y,id;
bool operator < (const node &nd)const{
if(x == nd.x) return y < nd.y;
return x < nd.x;
}
};
// node lis[N << 2]; int lsc = 0;
vector <node> nx[N];
void solve(){
cin >> n;
int minl = 0x3f3f3f3f;
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};
minl = min(minl,x[i] - r[i]);
}
if(minl < 0) minl = 0;
sort(s + 1,s + 1 + n);
// connect all possible circles with x = minl first
int pos = 0;
for(int i = 1;i <= n;i ++){
if(x[s[i].id] - r[s[i].id] <= minl) 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;
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();
}
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{
nx[id].push_back({x[u] - r[u],y[u],u});
// 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]});
}
G.push_back({y[u],u});
mxr = max(mxr,{x[u] + r[u],u});
}
for(int i = 1;i <= n;i ++){
if(nx[i].size() == 0) continue;
sort(nx[i].begin(),nx[i].end());
int las = 0;
for(int j = 0;j < nx[i].size();j ++){
if(j + 1 == nx[i].size() || (nx[i][j].x != nx[i][j + 1].x)){
G.clear();
for(int k = las;k <= j;k ++){
G.push_back({nx[i][k].y,nx[i][k].id});
}
G.push_back({y[s[i].id],s[i].id});
sort(G.begin(),G.end());
for(int k = 1;k < G.size();k ++){
ans.push_back({nx[i][j].x,G[k - 1].first,nx[i][j].x,G[k].first});
}
las = j + 1;
}
}
}
// 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: 19160kb
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: 1ms
memory: 17776kb
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: 18716kb
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: -100
Wrong Answer
time: 1ms
memory: 17804kb
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 58 68 88 95 27 24 27 29 35 24 35 88 18 55 18 55 38 0 38 68 7 24 7 82 7 82 7 88 95 68 95 81 24 0 24 81
result:
wrong answer Segment is degenerate