QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#222832 | #6639. Disk Tree | Nerovix | WA | 0ms | 3888kb | C++14 | 1.3kb | 2023-10-21 19:04:59 | 2023-10-21 19:04:59 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define ll long long
using namespace std;
const int maxn=2e5+10;
int x[maxn],r[maxn],y[maxn];
int n;
map<int,pair<vector<int>,vector<int>>>mp;
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>r[i];
mp[max(0,x[i]-r[i])].fi.pb(i);
mp[min((int)1e9,x[i]+r[i])].se.pb(i);
}
set<pair<int,int> >s;
int lx=-1,ly;
cout<<"YES\n";
for(auto p:mp){
int x=p.fi;
auto pfi=p.se.fi;
for(int i:pfi){
if(s.size()==0){
if(lx!=-1){
cout<<lx<<" "<<ly<<" "<<x<<" "<<y[i]<<"\n";
}
s.insert(mpr(y[i],i));
}
else{
auto it=s.lower_bound(mpr(y[i],(int)1e9));
if(it==s.end())--it;
cout<<x<<" "<<it->fi<<" "<<x<<" "<<y[i]<<"\n";
s.insert(mpr(y[i],i));
}
}
auto pse=p.se.se;
for(int i:pse){
s.erase(mpr(y[i],i));
if(s.size()==0){
lx=x,ly=y[i];
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3888kb
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: 0ms
memory: 3628kb
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: 3652kb
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 2 20 19 10 19 20 19 10 19 0
result:
ok answer = 1
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3816kb
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 7 82 7 82 7 24 18 82 18 55 24 24 24 0 27 55 27 29 35 55 35 88 38 88 38 68 58 68 88 95 95 95 95 81
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