QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123573#6639. Disk TreeinstallbWA 146ms32700kbC++144.2kb2023-07-12 21:51:292023-07-12 21:51:32

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:51:32]
  • 评测
  • 测评结果:WA
  • 用时:146ms
  • 内存:32700kb
  • [2023-07-12 21:51:29]
  • 提交

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[i],i});
                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: 1ms
memory: 18064kb

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

input:

2
1 1 1
3 3 1

output:

YES
2 1 2 3

result:

ok answer = 1

Test #3:

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

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: 1ms
memory: 17560kb

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

result:

ok answer = 1

Test #5:

score: 0
Accepted
time: 4ms
memory: 19340kb

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
488 714 488 783
927 697 927 914
977 709 977 914
406 40 406 265
420 163 420 265
432 132 432 265
498 190 498 265
260 710 260 854
284 746 284 854
312 265 312 438
366 422 366 438
530 734 530 992
554 781 554 992
599 901 599 992
613 797 613 99...

result:

ok answer = 1

Test #6:

score: 0
Accepted
time: 4ms
memory: 19504kb

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
2778 7991 2778 9798
2899 8690 2899 9798
2941 8806 2941 9798
3287 9131 3287 9798
3890 587 3890 647
1109 1326 1109 2717
4363 6830 4363 6858
55 7670 55 7903
178 7484 178 7670
7188 187 7188 1213
7384 110 7384 1213
7525 350 7525 1213
7948 424 79...

result:

ok answer = 1

Test #7:

score: 0
Accepted
time: 0ms
memory: 19396kb

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
48087 16699 48087 21821
49704 19338 49704 21821
7383 75412 7383 81086
47746 21821 47746 22290
37718 30750 37718 46942
38270 38309 38270 46942
39854 35058 39854 46942
42720 37079 42720 46942
47099 3780...

result:

ok answer = 1

Test #8:

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

input:

1000
558504245 246224785 100000000
971981730 913036757 1821458
198791767 482624549 5998171
540520619 353988177 8924682
183178222 46223569 9859905
118485076 22129062 7497235
274928891 417171180 372954
230079763 468235825 289869
859092765 562864738 5551376
129036518 743777318 3969979
265158223 3092933...

output:

YES
0 93982006 0 235938924
0 235938924 0 359002653
0 359002653 0 429721563
0 429721563 0 500334319
0 500334319 0 553121854
0 553121854 0 595275379
0 595275379 0 673089475
0 673089475 0 713751639
0 713751639 0 769665792
0 769665792 0 816264930
0 816264930 0 918989948
486240692 170833760 486240692 246...

result:

ok answer = 1

Test #9:

score: 0
Accepted
time: 0ms
memory: 18984kb

input:

3000
442876143 334276354 3627270
526253918 947313397 2498956
566692880 229330019 4243066
497859604 658736917 13012787
315969653 65582717 1400013
394215653 932651144 1655676
58249045 973232518 860150
860773683 959388251 1594726
23803673 921365885 5926749
730359196 818999592 1521282
971839312 22835235...

output:

YES
0 4543545 0 20450809
0 20450809 0 33689791
0 33689791 0 73749521
0 73749521 0 85019332
0 85019332 0 91838752
0 91838752 0 115835530
0 115835530 0 138290805
0 138290805 0 244652455
0 244652455 0 344420182
0 344420182 0 372703679
0 372703679 0 411886099
0 411886099 0 433135538
0 433135538 0 493352...

result:

ok answer = 1

Test #10:

score: 0
Accepted
time: 9ms
memory: 17988kb

input:

7000
601805179 978984160 464352
918208048 607538668 2214109
328147216 806677103 3901695
961794394 719893281 1114470
453816635 992288784 274949
778724702 692479905 1170018
169287513 886715521 576156
812072299 118324465 93778
726229729 150105801 3593039
368683874 642143790 1277375
40087476 151799345 4...

output:

YES
0 7669779 0 82305277
0 82305277 0 104534031
0 104534031 0 133505889
0 133505889 0 145494976
0 145494976 0 178650168
0 178650168 0 204712391
0 204712391 0 221426602
0 221426602 0 245488837
0 245488837 0 288398415
0 288398415 0 323305633
0 323305633 0 328807797
0 328807797 0 340684446
0 340684446 ...

result:

ok answer = 1

Test #11:

score: 0
Accepted
time: 11ms
memory: 18744kb

input:

10000
645 4710 5
1554 4072 7
6505 2760 1
6125 8212 11
9802 9537 3
6584 4356 6
1104 6649 23
4580 2623 20
3107 2460 1
4689 1662 2
7815 161 14
8718 3658 28
2900 63 15
1741 7296 44
8380 4608 50
2212 8514 4
7919 3069 17
1638 6057 3
504 9867 18
7869 8021 14
866 9239 5
3452 8042 4
9049 7222 4
4447 1004 5
9...

output:

YES
0 8 0 71
0 71 0 616
0 616 0 1146
0 1146 0 1314
0 1314 0 1592
0 1592 0 1751
0 1751 0 1799
0 1799 0 1883
0 1883 0 2188
0 2188 0 2481
0 2481 0 2550
0 2550 0 2631
0 2631 0 2676
0 2676 0 2756
0 2756 0 2887
0 2887 0 3106
0 3106 0 3323
0 3323 0 3437
0 3437 0 3584
0 3584 0 3695
0 3695 0 3784
0 3784 0 38...

result:

ok answer = 1

Test #12:

score: 0
Accepted
time: 62ms
memory: 24460kb

input:

100000
956095525 596102106 2
461544095 587257542 118
884402350 357055086 14228
547768407 186052059 263162
827807425 303694996 474924
692537425 44608243 131609
504660936 451030143 15134
207539367 899608364 20283
919236289 724317925 6
386476373 727023405 323
781914406 792770865 1064
411548762 2476126 ...

output:

YES
0 16414678 0 114863446
0 114863446 0 266626847
0 266626847 0 304414580
0 304414580 0 312730895
0 312730895 0 333397542
0 333397542 0 427209090
0 427209090 0 571603990
0 571603990 0 616424636
0 616424636 0 643298905
0 643298905 0 646455574
0 646455574 0 674631883
0 674631883 0 707448235
0 7074482...

result:

ok answer = 1

Test #13:

score: 0
Accepted
time: 146ms
memory: 29128kb

input:

200000
267774456 105702394 770
297991198 776424841 124
703700092 120262616 341808
212663821 221756923 367
195031049 705083745 66
692227605 63745620 1221
615879799 481139131 3053
93198187 239262367 141042
645539116 89213985 1679
312339485 547897747 2701
546940040 418847605 2
100457345 231142218 2
290...

output:

YES
0 36450043 0 65503887
0 65503887 0 103165813
0 103165813 0 113223272
0 113223272 0 121163888
0 121163888 0 231691420
0 231691420 0 240450858
0 240450858 0 271364932
0 271364932 0 287867208
0 287867208 0 359415760
0 359415760 0 407335778
0 407335778 0 442225971
0 442225971 0 541026964
0 541026964...

result:

ok answer = 1

Test #14:

score: 0
Accepted
time: 139ms
memory: 29720kb

input:

200000
890760596 387635202 407021
845949678 865384827 250
298937825 444813049 30
257079208 603496538 24935
825947861 514433442 276
664047255 283065064 651111
481691537 759981944 616
953630211 233077236 207
716089940 174481709 876827
807394429 737990862 50258
9195111 176890156 946
209723712 839382384...

output:

YES
0 23586061 0 29081244
0 29081244 0 49313954
0 49313954 0 61288319
0 61288319 0 72741002
0 72741002 0 84962436
0 84962436 0 136092710
0 136092710 0 160263492
0 160263492 0 168474053
0 168474053 0 218635420
0 218635420 0 266233086
0 266233086 0 301197220
0 301197220 0 333616539
0 333616539 0 40477...

result:

ok answer = 1

Test #15:

score: 0
Accepted
time: 124ms
memory: 30300kb

input:

200000
21940906 14228149 878
947616612 637746482 278
490310177 117451293 1714712
278642428 651582650 1
214397046 727562852 3
314365021 93147008 158746
367463298 30253119 650745
816993648 678947261 4384
503557517 182822048 1116
61881753 989787068 109052
632366340 971129473 26
870552310 805607887 5436...

output:

YES
0 31640168 0 94878040
0 94878040 0 114673404
0 114673404 0 133976538
0 133976538 0 138021782
0 138021782 0 144473048
0 144473048 0 175463994
0 175463994 0 179592469
0 179592469 0 219985608
0 219985608 0 230772950
0 230772950 0 287768048
0 287768048 0 292509612
0 292509612 0 305761966
0 305761966...

result:

ok answer = 1

Test #16:

score: 0
Accepted
time: 140ms
memory: 30976kb

input:

200000
81117 91365 1
68731 21152 3
37456 24002 2
37581 56006 3
52472 65837 1
68592 30967 2
37017 58189 11
21553 64504 95
94147 72332 80
82905 892 21
37593 40659 5
83451 10026 2
24925 11872 13
84418 48948 156
52378 43742 51
27379 10720 162
37042 54394 1
92324 20573 1
69506 96945 133
87826 40634 3
962...

output:

YES
0 741 0 1577
0 1577 0 2446
0 2446 0 4749
0 4749 0 5324
0 5324 0 5611
0 5611 0 6345
0 6345 0 6864
0 6864 0 7242
0 7242 0 8059
0 8059 0 8857
0 8857 0 9037
0 9037 0 10569
0 10569 0 11176
0 11176 0 11733
0 11733 0 12650
0 12650 0 13395
0 13395 0 14154
0 14154 0 15268
0 15268 0 15959
0 15959 0 16828
...

result:

ok answer = 1

Test #17:

score: 0
Accepted
time: 12ms
memory: 18752kb

input:

10000
126758371 588314899 812231
238086622 378023315 890058
477126060 14900711 1191393
511712433 35095827 204725
651796639 43378716 2018310
308442866 596282834 2328087
42294570 231322805 1602825
168464157 357054887 2277954
224671652 693289331 2062259
616695889 175688410 1253251
385431057 29127383 18...

output:

YES
0 1053491 0 21950698
0 21950698 0 29071213
0 29071213 0 42350620
0 42350620 0 63221024
0 63221024 0 70529176
0 70529176 0 84344160
0 84344160 0 98466030
0 98466030 0 112841976
0 112841976 0 119439557
0 119439557 0 126486661
0 126486661 0 140952914
0 140952914 0 147195943
0 147195943 0 169069673
...

result:

ok answer = 1

Test #18:

score: 0
Accepted
time: 19ms
memory: 19968kb

input:

40000
290669648 662085507 804601
669033554 119055358 638805
105668336 570987547 641107
70398923 679676225 1151529
67163601 217283316 655911
266292842 490670500 288695
332954119 213678087 316383
133514562 301390490 1150957
189198028 430695918 498385
52533444 508154472 662055
675557474 175423882 71076...

output:

YES
0 3898576 0 7023791
0 7023791 0 10876184
0 10876184 0 14518390
0 14518390 0 21171278
0 21171278 0 24950417
0 24950417 0 32148027
0 32148027 0 35669373
0 35669373 0 38900667
0 38900667 0 42087876
0 42087876 0 49175832
0 49175832 0 60111997
0 60111997 0 66792042
0 66792042 0 70483357
0 70483357 0 ...

result:

ok answer = 1

Test #19:

score: 0
Accepted
time: 57ms
memory: 23544kb

input:

79806
675311888 175949323 45152
668303725 415877398 705454
526993355 106652475 101518
306843353 465414670 733685
235164634 54490010 250702
237718215 128806833 416572
47406184 660535125 231461
217980403 334240174 311035
438155656 608919183 741482
175786440 138973185 691587
383453409 420621369 23780
1...

output:

YES
0 75115 0 2564757
0 2564757 0 4991138
0 4991138 0 7654178
0 7654178 0 10139465
0 10139465 0 12492643
0 12492643 0 14967837
0 14967837 0 22579503
0 22579503 0 25102875
0 25102875 0 27269094
0 27269094 0 32493546
0 32493546 0 34714044
0 34714044 0 39684135
0 39684135 0 47142938
0 47142938 0 498779...

result:

ok answer = 1

Test #20:

score: 0
Accepted
time: 143ms
memory: 32180kb

input:

199809
330527920 105087498 120223
601378677 222559216 191284
604605920 449476822 241005
435487497 286817733 303877
682929431 10980946 280834
393289259 673421713 256371
217818174 324382996 403684
307178253 324362921 334561
321290021 314861063 288503
661144513 394874427 31218
664021225 319719526 14923...

output:

YES
0 79477 0 3267733
0 3267733 0 4869837
0 4869837 0 6431437
0 6431437 0 8038686
0 8038686 0 11030533
0 11030533 0 14113479
0 14113479 0 18833700
0 18833700 0 20491240
0 20491240 0 23496141
0 23496141 0 26723859
0 26723859 0 29974279
0 29974279 0 31364131
0 31364131 0 34694473
0 34694473 0 36263968...

result:

ok answer = 1

Test #21:

score: -100
Wrong Answer
time: 120ms
memory: 32700kb

input:

200000
500000000 500000000 450000000
950000002 500000000 1
950000002 500014137 1
950000001 500028274 1
950000000 500042412 1
949999998 500056549 1
949999996 500070686 1
949999994 500084823 1
949999991 500098961 1
949999988 500113098 1
949999984 500127235 1
949999980 500141372 1
949999975 500155510 1...

output:

YES
0 499978794 0 499992931
0 499992931 0 500007069
0 500007069 0 500021206
50000004 499922245 50000004 500000000
50000004 500000000 50000004 500077755
50000009 499893971 50000009 500000000
50000009 500000000 50000009 500106029
50000013 499879833 50000013 500000000
50000013 500000000 50000013 500120...

result:

wrong answer Two disks cannot reach eachother