QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123556#6639. Disk TreeinstallbWA 2ms9624kbC++142.3kb2023-07-12 20:51:002023-07-12 20:51:02

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 20:51:02]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9624kb
  • [2023-07-12 20:51:00]
  • 提交

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];

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,flg = 0;
        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; flg = 0;
                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; flg = 1;
                    break;
                }
            }
        }
        if(id == -1 && i > 1) ans.push_back({mxr.first,y[mxr.second],x[u] - r[u],y[u]});
        else ans.push_back({x[u] - r[u],y[id],x[u] - r[u] + flg,y[u]});
        st.insert({y[u],u});
        mxr = max(mxr,{x[u] + r[u],u});
    }

    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: 7540kb

input:

3
1 0 3
10 10 6
0 5 1

output:

YES
0 0 0 5
4 0 5 10

result:

ok answer = 1

Test #2:

score: 0
Accepted
time: 2ms
memory: 7452kb

input:

2
1 1 1
3 3 1

output:

YES
2 1 3 3

result:

ok answer = 1

Test #3:

score: 0
Accepted
time: 1ms
memory: 7568kb

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 3 20
19 10 19 0
19 10 20 20

result:

ok answer = 1

Test #4:

score: 0
Accepted
time: 2ms
memory: 7508kb

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 8 24
7 24 8 82
18 82 18 55
24 24 24 0
27 55 27 29
35 55 36 88
38 88 38 68
58 68 88 95
95 95 95 81

result:

ok answer = 1

Test #5:

score: 0
Accepted
time: 2ms
memory: 9624kb

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 8 952
20 663 20 607
39 952 39 843
60 773 60 703
63 952 63 850
64 366 64 226
75 850 75 790
81 226 81 208
100 208 100 115
111 703 111 603
120 603 120 512
129 366 129 156
134 366 134 241
176 241 176 100
179 703 180 934
198 512 198 323...

result:

ok answer = 1

Test #6:

score: 0
Accepted
time: 1ms
memory: 7516kb

input:

200
2948 9798 687
3897 647 35
3918 587 28
1262 2717 206
1315 9524 20
2381 305 1000
4344 6858 20
6234 8949 53
5168 4772 85
5044 6109 158
72 7670 132
7300 1213 837
5427 2263 1000
1785 3009 276
6136 1421 43
1629 5620 29
6445 9489 242
8443 3141 1000
4118 4307 63
1874 5238 291
1964 5785 73
7794 3934 18
3...

output:

YES
0 1148 0 2852
0 2852 0 4653
0 4653 0 6162
0 6162 0 7670
55 7670 56 7903
87 7903 88 9469
113 9469 113 8944
139 4653 139 3990
178 7670 178 7484
265 1148 265 51
289 7484 289 6779
305 6162 305 5282
349 9469 349 9349
374 9469 375 9493
413 2852 413 1890
432 6162 432 5542
440 8944 440 8185
555 2852 555...

result:

ok answer = 1

Test #7:

score: -100
Wrong Answer
time: 2ms
memory: 7596kb

input:

300
42942 37079 222
49441 21821 1695
61023 31153 561
86630 26307 352
36940 78253 213
7841 81086 626
47425 22290 374
17694 68695 648
38259 64794 998
43599 46942 9662
9204 2816 1965
38652 83568 4057
4046 29001 1034
72591 63214 587
75984 64859 1112
70005 72177 576
34522 52126 652
56627 48785 1747
78820...

output:

YES
0 16007 0 24419
0 24419 0 39900
0 39900 0 58648
0 58648 0 69461
0 69461 0 79893
0 79893 0 99921
110 16007 110 7853
414 99921 414 91204
548 91204 548 90680
1003 99921 1003 92828
1725 39900 1725 32550
2213 58648 2213 46829
3012 32550 3012 29001
3149 58648 3149 47905
3325 79893 3325 73213
3840 2441...

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