QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#222832#6639. Disk TreeNerovixWA 0ms3888kbC++141.3kb2023-10-21 19:04:592023-10-21 19:04:59

Judging History

你现在查看的是最新测评结果

  • [2023-10-21 19:04:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3888kb
  • [2023-10-21 19:04:59]
  • 提交

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