QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123568#6639. Disk TreeinstallbWA 2ms9648kbC++143.3kb2023-07-12 21:24:022023-07-12 21:24:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-12 21:24:04]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9648kb
  • [2023-07-12 21:24:02]
  • 提交

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