QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#135229#6639. Disk TreeSolitaryDream#AC ✓396ms47640kbC++201.6kb2023-08-05 13:02:352023-08-05 13:02:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 13:02:36]
  • 评测
  • 测评结果:AC
  • 用时:396ms
  • 内存:47640kb
  • [2023-08-05 13:02:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int n;
struct Circle {
    int x, y, r;
};
bool operator<(Circle c1, Circle c2) {
    return c1.x < c2.x;
}
set<Circle> st;
map<int, vector<Circle>> mp;
signed main() {
    scanf("%lld", &n);
    vector<pair<int, Circle>> vec; 
    for (int i = 1; i <= n; ++i) {
        Circle c;
        scanf("%lld%lld%lld", &c.x, &c.y, &c.r);
        mp[min<int>(c.y + c.r, 1e9) * 2 + 1].push_back(c);
        mp[(c.y - c.r) * 2].push_back(c);
    }
    puts("YES");
    int lx = -1, ly = -1;
    for (auto it = mp.rbegin(); it != mp.rend(); ++it) {
        int hei = it->first >> 1;
        sort(it->second.begin(), it->second.end());
        if (!st.empty()) {
            int x = st.begin()->x;
            auto ps = it->second.begin();
            while (ps != it->second.end() && ps->x < x) ++ps;
            reverse(it->second.begin(), ps);
        }
        for (auto cir : it->second) if (it->first & 1) {  // insert
            // printf("Insert %lld %lld %lld\n", cir.x, cir.y, cir.r);
            if (st.empty()) {
                if (lx != -1) {
                    printf("%lld %lld %lld %lld\n", lx, ly, cir.x, hei);
                }
            } else {
                auto ps = st.insert(cir).first;
                if (ps != st.begin()) printf("%lld %lld %lld %lld\n", prev(ps)->x, hei, cir.x, hei);
                else printf("%lld %lld %lld %lld\n", next(ps)->x, hei, cir.x, hei);
            }
            st.insert(cir);
        } else {
            lx = cir.x; ly = hei;
            st.erase(cir);
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

3
1 0 3
10 10 6
0 5 1

output:

YES
10 6 0 6
10 4 1 3

result:

ok answer = 1

Test #2:

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

input:

2
1 1 1
3 3 1

output:

YES
3 2 1 2

result:

ok answer = 1

Test #3:

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

input:

5
10 10 10
2 0 1
20 20 1
3 20 1
20 0 1

output:

YES
3 21 20 21
3 20 10 20
10 1 2 1
10 1 20 1

result:

ok answer = 1

Test #4:

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

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
98 98 45 98
45 92 17 92
98 85 99 85
45 78 48 78
48 65 28 65
28 45 17 34
17 31 29 31
17 18 0 18
0 10 34 10

result:

ok answer = 1

Test #5:

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

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
553 1016 375 1016
553 1014 997 1014
375 1012 67 1012
67 990 235 990
235 974 293 974
553 948 777 948
553 938 656 938
777 930 841 930
375 908 468 908
67 903 116 903
553 903 601 903
235 893 296 893
656 864 680 864
841 856 910 856
116 855 51 855
296 846 384 846
680 846 771 846
116 818 32 818
384 811...

result:

ok answer = 1

Test #6:

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

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
2948 10421 9505 10421
2948 10253 5225 10253
5225 10194 7511 10194
5225 10135 6125 10135
7511 10062 8438 10062
2948 9925 1844 9925
5225 9835 6062 9835
5225 9731 6445 9731
1844 9613 231 9613
231 9604 1756 9604
231 9581 462 9581
462 9544 1315 9544
231 9413 413 9413
413 9287 456 9287
8438 9282 9928 ...

result:

ok answer = 1

Test #7:

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

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
48815 104974 70298 104974
48815 102828 11003 102828
11003 102195 31276 102195
70298 101921 82276 101921
11003 101761 1522 101761
82276 100285 96182 100285
48815 97023 59314 97023
70298 96418 84773 96418
11003 95651 21145 95651
84773 93033 90608 93033
70298 92477 81067 92477
48815 92327 56990 923...

result:

ok answer = 1

Test #8:

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

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
55464040 1000000000 135167617 1000000000
135167617 1000000000 161970667 1000000000
161970667 1000000000 192812726 1000000000
192812726 1000000000 309812694 1000000000
309812694 1000000000 500090508 1000000000
500090508 1000000000 593944789 1000000000
593944789 1000000000 633662940 1000000000
633...

result:

ok answer = 1

Test #9:

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

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
3784037 1000000000 125449154 1000000000
125449154 1000000000 191975431 1000000000
191975431 1000000000 287489808 1000000000
287489808 1000000000 396056665 1000000000
396056665 1000000000 415389805 1000000000
415389805 1000000000 434867203 1000000000
434867203 1000000000 487894493 1000000000
4878...

result:

ok answer = 1

Test #10:

score: 0
Accepted
time: 10ms
memory: 5376kb

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
25810964 1000000000 113448525 1000000000
113448525 1000000000 124801077 1000000000
124801077 1000000000 136153625 1000000000
136153625 1000000000 158575792 1000000000
158575792 1000000000 167675229 1000000000
167675229 1000000000 259179070 1000000000
259179070 1000000000 358282850 1000000000
358...

result:

ok answer = 1

Test #11:

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

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
4005 10613 8723 10613
4005 10570 5630 10570
4005 10352 115 10352
5630 10338 7391 10338
8723 10094 9847 10094
115 10086 2240 10086
115 10076 1195 10076
115 10056 845 10056
5630 10051 6424 10051
1195 10047 1806 10047
845 10032 1032 10032
6424 10031 6596 10031
115 10025 534 10025
2240 10018 2419 10...

result:

ok answer = 1

Test #12:

score: 0
Accepted
time: 159ms
memory: 25548kb

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
232360922 1000000000 307348163 1000000000
307348163 1000000000 363099476 1000000000
363099476 1000000000 384949315 1000000000
384949315 1000000000 428850796 1000000000
428850796 1000000000 453169010 1000000000
453169010 1000000000 500444907 1000000000
500444907 1000000000 591119979 1000000000
59...

result:

ok answer = 1

Test #13:

score: 0
Accepted
time: 352ms
memory: 47372kb

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
25187894 1000000000 41705279 1000000000
41705279 1000000000 50229233 1000000000
50229233 1000000000 57125765 1000000000
57125765 1000000000 100444869 1000000000
100444869 1000000000 163120908 1000000000
163120908 1000000000 205405665 1000000000
205405665 1000000000 217296629 1000000000
217296629...

result:

ok answer = 1

Test #14:

score: 0
Accepted
time: 365ms
memory: 47400kb

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
7306570 1000000000 43440298 1000000000
43440298 1000000000 123781324 1000000000
123781324 1000000000 131916136 1000000000
131916136 1000000000 186977576 1000000000
186977576 1000000000 211752313 1000000000
211752313 1000000000 245684432 1000000000
245684432 1000000000 265648392 1000000000
265648...

result:

ok answer = 1

Test #15:

score: 0
Accepted
time: 357ms
memory: 47388kb

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
23676744 1000000000 31817318 1000000000
31817318 1000000000 86005822 1000000000
86005822 1000000000 105410695 1000000000
105410695 1000000000 173606729 1000000000
173606729 1000000000 217228204 1000000000
217228204 1000000000 242743053 1000000000
242743053 1000000000 248676075 1000000000
2486760...

result:

ok answer = 1

Test #16:

score: 0
Accepted
time: 356ms
memory: 30944kb

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
69711 100167 20069 100167
69711 100167 88592 100167
69711 100166 75353 100166
20069 100164 47349 100164
20069 100162 13024 100162
69711 100159 74718 100159
13024 100158 10463 100158
13024 100153 15764 100153
20069 100138 27678 100138
20069 100132 25055 100132
27678 100131 36306 100131
20069 1001...

result:

ok answer = 1

Test #17:

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

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
301879853 696327339 504244798 696327339
504244798 696293288 574316594 696293288
301879853 696256121 148370459 696256121
148370459 696198811 77416572 696198811
301879853 696097059 441531865 696097059
574316594 696081693 645014380 696081693
504244798 696041403 518706071 696041403
301879853 6960179...

result:

ok answer = 1

Test #18:

score: 0
Accepted
time: 53ms
memory: 12428kb

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
514574633 698304942 143870264 698304942
143870264 698218824 322157622 698218824
143870264 698187748 10627269 698187748
322157622 698142450 420405599 698142450
10627269 698095451 60110935 698095451
514574633 698056210 546227986 698056210
143870264 698029268 266566067 698029268
514574633 698003111...

result:

ok answer = 1

Test #19:

score: 0
Accepted
time: 133ms
memory: 21352kb

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
57161213 698745394 104220567 698745394
104220567 698740482 198344267 698740482
57161213 698727848 7877738 698727848
198344267 698724061 316782955 698724061
316782955 698719381 324466574 698719381
104220567 698717017 128832540 698717017
198344267 698711421 240103953 698711421
324466574 698704535 ...

result:

ok answer = 1

Test #20:

score: 0
Accepted
time: 396ms
memory: 47568kb

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
42490452 699250306 563826942 699250306
563826942 699249350 631254747 699249350
631254747 699246021 632903876 699246021
42490452 699232745 242921381 699232745
242921381 699218491 244528595 699218491
42490452 699203514 84699412 699203514
244528595 699201160 491858888 699201160
84699412 699198454 1...

result:

ok answer = 1

Test #21:

score: 0
Accepted
time: 152ms
memory: 47456kb

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
499982328 950000003 499996466 950000003
499996466 950000003 500010603 950000003
499982328 950000002 499968191 950000002
500010603 950000002 500024740 950000002
499968191 950000001 499954054 950000001
500024740 950000001 500038877 950000001
499968191 950000000 500000000 950000000
500038877 950000...

result:

ok answer = 1

Test #22:

score: 0
Accepted
time: 157ms
memory: 25252kb

input:

200000
1666 1666 1666
6664 1666 1666
11662 1666 1666
16660 1666 1666
21658 1666 1666
26656 1666 1666
31654 1666 1666
36652 1666 1666
41650 1666 1666
46648 1666 1666
51646 1666 1666
56644 1666 1666
61642 1666 1666
66640 1666 1666
71638 1666 1666
76636 1666 1666
81634 1666 1666
86632 1666 1666
91630 1...

output:

YES
1666 3332 6664 3332
6664 3332 11662 3332
11662 3332 16660 3332
16660 3332 21658 3332
21658 3332 26656 3332
26656 3332 31654 3332
31654 3332 36652 3332
36652 3332 41650 3332
41650 3332 46648 3332
46648 3332 51646 3332
51646 3332 56644 3332
56644 3332 61642 3332
61642 3332 66640 3332
66640 3332 71...

result:

ok answer = 1

Test #23:

score: 0
Accepted
time: 194ms
memory: 29356kb

input:

200000
1276 2177 1666
6143 1271 1666
12177 1577 1666
17105 1415 1666
21414 1758 1666
27078 1291 1666
31751 1856 1666
36681 2166 1666
42165 1914 1666
46298 2207 1666
51434 1925 1666
56782 1717 1666
61708 1408 1666
66612 1280 1666
71599 2168 1666
76405 1971 1666
81489 1694 1666
86696 2187 1666
91352 1...

output:

YES
4245470 3887 14555353 3887
14555353 3887 15195554 3887
15195554 3887 31469027 3887
31469027 3887 31714383 3887
31714383 3887 41570042 3887
41570042 3887 47082419 3887
47082419 3887 51700752 3887
51700752 3887 53634945 3887
53634945 3887 59127726 3887
59127726 3887 60917396 3887
60917396 3887 799...

result:

ok answer = 1

Test #24:

score: 0
Accepted
time: 183ms
memory: 47640kb

input:

200000
1666 1666 1666
6588 2534 1666
11510 3402 1666
16432 4270 1666
21354 5138 1666
26276 6005 1666
31198 6873 1666
36120 7741 1666
41043 8609 1666
45965 9477 1666
50887 10345 1666
55809 11213 1666
60731 12081 1666
65653 12949 1666
70575 13817 1666
75497 14684 1666
80419 15552 1666
85341 16420 1666...

output:

YES
984410574 173580315 984405652 173580315
984405652 173579447 984400730 173579447
984400730 173578579 984395808 173578579
984395808 173577711 984390886 173577711
984390886 173576843 984385963 173576843
984385963 173575975 984381041 173575975
984381041 173575107 984376119 173575107
984376119 173574...

result:

ok answer = 1

Test #25:

score: 0
Accepted
time: 170ms
memory: 47372kb

input:

200000
1666 1666 1666
1666 6664 1666
1666 11662 1666
1666 16660 1666
1666 21658 1666
1666 26656 1666
1666 31654 1666
1666 36652 1666
1666 41650 1666
1666 46648 1666
1666 51646 1666
1666 56644 1666
1666 61642 1666
1666 66640 1666
1666 71638 1666
1666 76636 1666
1666 81634 1666
1666 86632 1666
1666 91...

output:

YES
1666 999595002 1666 999593336
1666 999590004 1666 999588338
1666 999585006 1666 999583340
1666 999580008 1666 999578342
1666 999575010 1666 999573344
1666 999570012 1666 999568346
1666 999565014 1666 999563348
1666 999560016 1666 999558350
1666 999555018 1666 999553352
1666 999550020 1666 999548...

result:

ok answer = 1

Test #26:

score: 0
Accepted
time: 165ms
memory: 47400kb

input:

200000
1238 1279 1666
1911 6266 1666
1278 11483 1666
1657 16880 1666
1637 22064 1666
1629 26455 1666
2087 31415 1666
1150 36477 1666
2020 41228 1666
1277 46249 1666
1331 51188 1666
1274 56871 1666
1709 61810 1666
1509 66281 1666
1922 71932 1666
2188 76257 1666
1947 81675 1666
2124 86511 1666
1231 91...

output:

YES
2118 999594891 1259 999593270
1259 999589938 1833 999588543
1833 999585211 1202 999583733
1202 999580401 1552 999578705
1552 999575373 2156 999573685
2156 999570353 2121 999568645
2121 999565313 1250 999563119
1250 999559787 1265 999558342
1265 999555010 1262 999553563
1262 999550231 1771 999548...

result:

ok answer = 1

Test #27:

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

input:

2
1000000000 1000000000 1000000000
0 0 1

output:

YES
1000000000 1 0 1

result:

ok answer = 1

Test #28:

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

input:

2
1000000000 1000000000 500000000
0 1000000000 499999999

output:

YES
0 1000000000 1000000000 1000000000

result:

ok answer = 1

Test #29:

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

input:

2
0 1000000000 499999999
0 0 500000000

output:

YES
0 500000001 0 500000000

result:

ok answer = 1

Test #30:

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

input:

2
1000000000 1000000000 499999999
1000000000 0 500000000

output:

YES
1000000000 500000001 1000000000 500000000

result:

ok answer = 1