QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #838990 | #3324. Joining Flows | yqr | AC ✓ | 13ms | 1560kb | C++23 | 1.8kb | 2025-01-01 10:14:28 | 2025-01-01 10:14:29 |
Judging History
answer
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
namespace IO {
constexpr int bufsize = 230005;
char buf[bufsize], *f1, *f2;
char gtchar() {return f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++;}
template<typename T> void read(T &ret)
{
int f = ret = 0;
char ch = gtchar();
while(!isdigit(ch)) f = ch == '-', ch = gtchar();
while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
if(f) ret = -ret;
}
template<typename T, typename ...t> void read(T &a, t &...b) {read(a), read(b...);}
}using IO::read;
typedef long long ll;
typedef unsigned long long ull;
constexpr int maxn = 15;
int n, q, l[maxn], r[maxn], p[maxn];
ll stao, sphi, t[maxn];
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
read(n);
for(int i = 1; i <= n; i++) read(t[i], l[i], r[i]), p[i] = i,
r[i] -= l[i], stao += t[i] * l[i], sphi += l[i];
read(q);
// printf("%lld %lld\n", stao, sphi);
for(int i = 1; i <= q; i++)
{
ll tao, phi;
read(tao, phi), tao *= phi;
// printf("tao:%lld\n", tao);
std::sort(p + 1, p + 1 + n, [](auto a, auto b) {return t[a] < t[b];});
ll nt = stao, np = sphi;
for(int j = 1; j <= n && np < phi; j++)
{
ll tmp = std::min<ll>(r[p[j]], phi - np);
// printf("%d:%lld\n", p[j], tmp);
nt += t[p[j]] * tmp;
np += tmp;
}
// printf("%lld\n", np);
if(np != phi || tao < nt)
{
puts("no");
continue;
}
// printf("min:%lld\n", nt);
nt = stao, np = sphi;
std::sort(p + 1, p + 1 + n, [](auto a, auto b) {return t[a] > t[b];});
for(int j = 1; j <= n && np < phi; j++)
{
ll tmp = std::min<ll>(r[p[j]], phi - np);
nt += t[p[j]] * tmp;
np += tmp;
}
if(tao > nt)
{
puts("no");
continue;
}
// printf("max:%lld\n", nt);
puts("yes");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1336kb
input:
1 608402 14432 275837 20 608403 263726 608403 56193 608401 228691 608402 126790 608401 225150 608401 52782 608402 117885 608401 225137 608403 237582 608402 258317 608403 110221 608402 161901 608401 195043 608402 49683 608403 60605 608403 236611 608402 75979 608403 80649 608402 246088 608402 262590
output:
no no no yes no no yes no no yes no yes no yes no no yes no yes yes
result:
ok 20 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 1308kb
input:
2 543316 38827 439591 343059 2974 92662 10 834504 5716 501377 910402 334753 496560 997914 121517 474222 669503 469890 366698 301503 268945 296556 31740 969788 516687 597259 77428
output:
no no no no no no no no no no
result:
ok 10 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 1244kb
input:
3 4095 190429 773852 86757 599809 758147 350819 38107 397634 10 361026 441870 434961 136989 303353 388344 43575 535053 332866 289436 33374 128274 480734 554629 823504 218275 876443 989854 863565 111935
output:
no no no no no no no no no no
result:
ok 10 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 1240kb
input:
4 371652 344973 801785 213755 666588 718375 440533 573275 620602 935346 519896 920446 10 533596 299513 107154 716137 961859 297852 115369 137162 866342 999628 86884 52086 809064 424350 839656 897577 30405 726935 533851 812423
output:
no no no no no no no no no no
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 1336kb
input:
5 331952 247301 937256 993245 484048 761841 850090 416145 853529 3671 29264 259024 261453 461074 902049 10 190718 572937 521388 834523 885179 496934 178715 102878 649039 428441 588870 307275 34192 821234 536688 193906 375571 476105 214300 745347
output:
no no no no no no no no no no
result:
ok 10 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 1296kb
input:
6 759770 220443 339926 530356 9590 449387 831296 681355 720838 914163 816989 931865 914066 100391 740545 50826 427187 700601 10 444454 952399 726202 596526 499265 571900 257198 133529 381105 814720 413870 933006 775029 876335 56458 641699 610057 511556 667186 590710
output:
no no no no no no no no no no
result:
ok 10 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 1248kb
input:
7 89108 112874 128594 159104 15677 698233 749717 79923 215491 66914 212385 386648 968262 207743 933483 294599 203841 974346 145797 299897 324612 10 853049 155031 659445 708817 421625 244698 700553 797150 781856 174236 706096 426479 518821 520980 565447 883501 54033 620923 49282 231426
output:
no no no no no no no no no no
result:
ok 10 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 1244kb
input:
8 103206 104339 441516 88245 101128 797858 704385 420100 575508 818413 421394 447516 139219 1215 520490 243807 151029 905655 709888 233345 331686 363544 2033 886882 10 19272 362302 106941 742116 751566 746732 491821 551656 376479 20388 789661 340185 599297 769877 943326 798636 563434 629963 817430 6...
output:
no no no no no no no no no no
result:
ok 10 lines
Test #9:
score: 0
Accepted
time: 0ms
memory: 1312kb
input:
9 611963 402084 874585 431246 56951 567546 349632 458959 740148 563995 39005 422934 188425 241200 434501 699193 446356 724060 848383 159833 771090 402850 735158 802814 498805 42622 899280 10 86043 969149 420062 935186 132133 959070 508426 59914 870544 465451 935792 512280 239604 113677 35785 828942 ...
output:
no no no no no no no no no no
result:
ok 10 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 1276kb
input:
10 526987 179533 563178 719484 677284 888265 618246 245646 308821 721854 169584 512399 710992 77507 571861 636299 139862 175366 116435 65749 720607 56584 27452 624887 240445 523335 787178 995669 142697 628846 10 451280 751264 719757 463991 601821 534 422551 241111 235126 671003 106836 442430 537967 ...
output:
no no no no no no no no no no
result:
ok 10 lines
Test #11:
score: 0
Accepted
time: 6ms
memory: 1540kb
input:
2 964357 1874 107611 553499 9972 461790 100000 556514 255259 897591 61365 555823 331035 555602 365957 864285 40941 727120 254651 691176 321136 555875 323825 557032 217875 592627 19677 555700 349504 556181 287056 588808 505209 917781 121370 555485 387330 921326 95212 559605 126068 566327 60015 556672...
output:
no yes no no no yes no no no no no no no no no no no no no no no no no yes yes no yes no yes yes no no no yes no yes no yes no no yes yes no no no yes no no no yes no no no no no yes no no yes no yes no no no no no no no no no no no no no no no no no no no no yes no no no no yes no no no yes no no n...
result:
ok 100000 lines
Test #12:
score: 0
Accepted
time: 7ms
memory: 1548kb
input:
3 351690 47836 309713 205060 3808 488698 955287 25456 421617 100000 255782 514797 590960 937348 263401 447567 599377 917338 886397 460602 262822 452061 841023 277696 264513 645736 845166 288145 272440 387531 709247 710174 725762 138244 271729 704002 397590 992614 883883 444376 382666 147021 262830 4...
output:
no no no no yes no yes no yes no yes no no no no no no yes no no no no yes no no no no no no yes no no yes yes no yes no no no yes no no no no no yes no no no yes no yes yes no yes no no no no yes no no yes no no no no no no no no no no yes no yes no no no yes no yes no yes no no yes no no no no no ...
result:
ok 100000 lines
Test #13:
score: 0
Accepted
time: 8ms
memory: 1560kb
input:
4 148365 56002 157104 590532 389 401923 153296 10466 172427 941560 11154 370451 100000 272404 443036 629619 169285 198507 181096 497867 119017 307918 498712 524897 963894 551045 135224 321195 523295 180371 302388 288614 466824 572880 143233 743782 657100 777842 322547 270776 440782 196835 188052 762...
output:
no no no no no no no no no no yes no no no no yes no no no no no yes no no no no no yes no no no no no no no no no no no no no yes no no no no no no no no yes yes no yes no yes no no yes yes yes no no no no no yes yes no no no no no yes no no no no no yes yes no no no yes no no yes no no no no no no...
result:
ok 100000 lines
Test #14:
score: 0
Accepted
time: 9ms
memory: 1524kb
input:
5 31958 23434 77232 704760 2673 314345 549889 4745 180832 355903 11680 384783 368606 21468 318624 100000 174947 126514 573217 211280 314482 538202 348859 855551 318181 577685 172043 108981 180047 103092 304666 446814 319679 595375 502079 965937 400469 91335 562855 671372 590723 243715 355473 884653 ...
output:
no no no no no no no no no no no no yes no no no no no no no no no no no no no yes no no no no no no no yes no no no no no yes yes no yes yes no no no yes no no no no no yes yes no no no no no no yes no no no yes no no no yes yes no no no yes yes no yes no no no yes no no yes no no yes no no yes no ...
result:
ok 100000 lines
Test #15:
score: 0
Accepted
time: 6ms
memory: 1508kb
input:
6 648221 589 316209 137644 12366 150488 986302 2706 215244 647442 27189 94839 263729 14499 308087 464251 31343 233509 100000 389263 916795 263464 283321 751443 533741 367927 847006 291567 604732 263509 340170 336692 143296 266374 527741 263534 385548 436755 95359 410808 999991 263516 354039 263548 4...
output:
no no yes no no no no no no no no no no no no no no no yes no yes yes yes no no no yes no no yes no no no no no no no yes no no no yes no no no no no yes no yes no no no no no yes yes no yes no no yes no yes no yes no no no yes no no yes no yes yes no no no no no no no no no no no no yes no yes no y...
result:
ok 100000 lines
Test #16:
score: 0
Accepted
time: 10ms
memory: 1552kb
input:
7 818234 2016 218594 815966 382 25279 894579 4405 52868 253107 24536 184942 557293 37353 160220 502421 4790 109954 34969 25635 31751 100000 696540 433005 605303 193346 637248 227471 360542 390160 613587 671972 472059 594033 686095 468116 583840 175641 506415 135088 657656 569359 648412 605417 585188...
output:
yes yes no no yes no yes no yes yes no no yes yes no yes no no yes yes no yes no no no no no no no no yes no no yes no yes yes no no no no no no yes yes yes no yes no no no no yes no yes no yes yes no no no no no yes no yes yes no no no yes no no no no no no no yes yes yes no yes no no yes no yes no...
result:
ok 100000 lines
Test #17:
score: 0
Accepted
time: 11ms
memory: 1512kb
input:
8 599244 37809 188927 683543 12512 48383 642219 2845 174088 736397 11948 163468 693895 1450 191636 451292 10719 78050 732020 7331 53906 33387 1730 21029 100000 533856 298539 670738 159623 698051 338001 697202 424740 697615 377603 684983 203851 686668 616734 607346 686512 688146 596897 684957 203745 ...
output:
no no no no no no yes no no no no yes no no no no no yes no yes yes yes no no no yes no no no no no yes no no no no yes no no yes no no no no no no no no no yes no yes no yes no no no no yes yes yes no no no yes no no no no yes no no no no no no no yes no no no no no no yes no yes yes yes no no no y...
result:
ok 100000 lines
Test #18:
score: 0
Accepted
time: 12ms
memory: 1504kb
input:
9 65029 1868 32759 137727 21484 72748 333579 20837 48994 94034 6045 26091 585970 17197 115818 662568 3293 203612 209106 9618 11109 255567 10575 118502 934999 5952 165826 100000 615339 648511 677398 519747 617431 644760 271146 130608 674599 536166 653569 586217 603152 173077 502075 744656 560436 7450...
output:
no yes yes no no yes no no yes no no yes yes no no no no yes no yes no no yes no no no no yes no no yes no no no no no no no no yes no no yes yes yes yes no no no no no yes no yes no no yes yes no no yes no no no no no yes no no no no no no no yes yes no yes yes no yes no yes yes no no no no yes no ...
result:
ok 100000 lines
Test #19:
score: 0
Accepted
time: 13ms
memory: 1544kb
input:
10 971201 2324 9663 7011 13742 25576 882231 3605 174400 63319 1937 2703 153815 5755 24130 75110 24326 76727 318183 4860 27701 727324 4044 142697 53269 8086 60257 876686 17426 168036 100000 766311 427855 461661 456717 763490 461230 259134 113813 572892 622321 574598 625772 529078 545113 715090 601083...
output:
no no no no no no no no no no no no no yes no no no no yes yes no no no no no no no no no yes yes no no yes no yes yes no yes no no no yes no no no no no yes yes no yes no yes no no yes no no no no no no no yes no no no no no no yes no no no no no no no no no no no no yes no no no no no yes no no no...
result:
ok 100000 lines
Test #20:
score: 0
Accepted
time: 0ms
memory: 1332kb
input:
2 895439 12501 35800 802243 42201 197190 51 512578 371165 993753 170453 816562 232990 449305 423434 988471 192470 170453 993753 429770 442681 823541 54702 816562 232991 371165 512578 54702 823541 823542 54703 232990 816563 807800 209690 256289 742330 816564 232991 816563 232990 511359 331251 898610 ...
output:
no no no no no no no yes no no no yes no yes no no yes no no no no no no no no no yes no yes no no no no no no yes no no no no yes no yes no no yes yes no yes no no
result:
ok 51 lines
Test #21:
score: 0
Accepted
time: 0ms
memory: 1336kb
input:
2 132516 42924 71220 682119 18143 249270 75 299502 586707 373359 470646 195569 898506 559985 320491 459162 382697 549603 32867 295802 61068 338673 53337 295804 61068 292194 601381 295804 61066 335991 534150 559986 320491 320490 559985 235323 746718 705969 248906 223994 801225 534150 335991 898506 19...
output:
no no no no no no yes no yes no no no no no no no no no no no no no no no no no no yes no no yes yes no no no no yes no no no no no no no no no no no yes no yes no no no no no no yes no no no yes yes no no no yes yes yes no no no no no no
result:
ok 75 lines
Test #22:
score: 0
Accepted
time: 0ms
memory: 1228kb
input:
3 37326 12603 480846 827626 26009 235667 846482 13415 169194 98 364189 91578 402177 885707 307355 729929 641045 52028 402178 885707 409808 547446 988513 51420 402178 885707 195396 260135 156081 325660 402179 885706 52027 976980 307356 729928 65132 780405 641047 52028 718382 495853 641046 52027 97697...
output:
no no no yes yes yes no yes yes yes no no yes no yes no yes no no yes no yes no yes yes yes yes yes yes no no yes no no no yes no no yes yes yes yes yes yes no no yes no yes yes no no yes no no no no no no yes no yes no no no no yes no no no no no yes no no yes yes yes yes yes no yes no no no yes ye...
result:
ok 98 lines
Test #23:
score: 0
Accepted
time: 0ms
memory: 1284kb
input:
3 618280 662 7630 101079 5360 389471 697139 12671 336281 50 687653 342304 686268 349271 379775 733382 523432 18694 687654 342303 687653 342303 379774 733382 535397 439647 687653 342302 18693 523433 733382 379774 523433 18694 686270 349272 523432 18693 379774 733381 523433 18692 379774 733382 349271 ...
output:
no yes no yes no yes yes yes no no no yes no no yes no yes no no yes yes yes no no no no yes no yes yes no no no yes no no yes no yes no no yes no yes no no no no no yes
result:
ok 50 lines
Test #24:
score: 0
Accepted
time: 0ms
memory: 1276kb
input:
10 62696 4483 14788 837284 4657 47821 406621 7220 85460 173770 9449 154599 884745 1342 53100 517609 8100 114840 795810 5877 123941 561638 889 135124 108880 4544 16156 714186 4097 27961 429 53850 926057 478995 104110 464877 493392 265644 863436 711956 322164 337272 958642 340029 402706 523728 773790 ...
output:
no yes yes no yes no no no no yes no yes no no yes yes yes no no no no no no yes no yes no no yes no no no no yes yes no no no yes no yes yes no no no no no no yes no no no no no no no no no no no yes no yes yes no no no no no no no yes no no yes no yes yes no no no no no no no no yes no no no yes n...
result:
ok 429 lines
Test #25:
score: 0
Accepted
time: 0ms
memory: 1340kb
input:
10 920408 3696 35088 777791 340 69338 696456 5433 143429 11059 3318 140930 420431 4420 42360 637143 5030 27138 232868 556 34160 566190 3934 123174 227778 8827 75213 404312 2052 134842 301 571808 621674 157307 112818 471921 37606 372984 997687 145376 689980 369485 940912 645677 455281 675970 68997 59...
output:
yes no yes no no no yes no no yes no yes yes no yes yes yes no yes yes yes yes yes yes no no yes yes no yes no yes no yes no no no no yes yes yes no no no no no yes no no no yes no no no no no yes no no no yes no no yes yes no yes no yes yes no no no yes no yes yes yes no yes no no yes no no yes yes...
result:
ok 301 lines
Test #26:
score: 0
Accepted
time: 0ms
memory: 1300kb
input:
2 197956 17593 408623 769327 21510 134175 45 430133 226529 386797 475996 226529 430132 46569 430133 512260 39104 26961 742957 339194 542798 339193 542798 512259 39104 339195 542798 226529 430133 237998 773594 226530 430134 430133 46569 226529 430133 339194 542797 512259 39103 339195 542799 512258 39...
output:
yes no no no yes no no no yes no no no no no no yes no no yes no no no no no no no no no no no no no no no no yes no no no no no no yes no no
result:
ok 45 lines
Test #27:
score: 0
Accepted
time: 0ms
memory: 1276kb
input:
2 245290 32218 429240 821222 4477 140747 45 387505 569988 251235 433717 224345 984523 315557 36695 251235 433718 387504 569987 315556 36696 984523 224345 387504 569986 327105 333119 387505 569986 403645 28687 251234 433717 333119 327105 251234 433718 259085 852511 315557 36696 315558 36695 109035 99...
output:
no yes no no no no yes no no yes yes no no yes no no yes no no no no no no no no yes yes no no yes no no no no no no no no yes no no no yes no no
result:
ok 45 lines
Test #28:
score: 0
Accepted
time: 0ms
memory: 1332kb
input:
3 698679 3684 70487 575003 13775 33464 548304 2230 21919 178 571712 39378 157512 142928 19689 595120 266505 302088 710680 113283 536280 150123 52504 428784 167315 481176 453132 177670 426408 188805 402210 200164 315024 37195 571713 39378 111585 105008 595119 19690 572808 59068 32815 357072 78756 148...
output:
no no no no no no no no no no no no yes no yes no no no no no no no yes no no no no no no no no no no no no no no no no no no no no no no no no no no no no no yes no no no no no no no no yes no no no no no no no no no no no no no no no no no no yes no no no no no no no no no no no no no no no no no ...
result:
ok 178 lines
Test #29:
score: 0
Accepted
time: 0ms
memory: 1300kb
input:
3 716883 30676 30850 866139 16629 38477 659048 1245 31720 146 113796 503525 637188 89925 725075 79025 725076 79024 73737 778766 869275 65916 766521 48551 948300 60423 766521 48550 725059 79198 725059 79199 766522 48549 359700 159297 725057 79198 755562 101047 60423 948300 625878 91550 798316 71775 7...
output:
no no no no no no yes no no yes yes no no no no no no no no no no no no no no no no no no no no no no no yes no no no no no yes no no no no no no no no no no no no no no no no no no yes no no no no no no no no no no no yes no no no no no no yes no no no no no no no no yes no yes no no no no no no ye...
result:
ok 146 lines
Test #30:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
7 70993 8047 30859 149383 89 79064 900048 5758 49657 610281 1738 25882 383441 11070 107170 286155 2278 20054 502376 7139 198805 244 41478 815238 432457 511490 423896 36118 217203 155681 388557 467593 442933 38223 376486 443449 287290 58931 798803 227448 184742 155502 356670 468084 340994 648684 8572...
output:
no no no yes no yes yes yes no no no no no yes no no no no no no no no no yes yes yes no no yes yes no no no no yes yes no yes no yes no no yes yes no no no yes no no yes no no no no no yes no no no no no no no no no no no no no no no yes no no no no no yes no no no no yes yes no no yes no no no no ...
result:
ok 244 lines
Test #31:
score: 0
Accepted
time: 0ms
memory: 1324kb
input:
7 361212 11732 131770 123130 7175 17009 465737 3306 105686 102040 3479 6507 359464 2314 60359 985583 13234 194727 585907 7891 45834 276 199517 240076 399033 120037 35947 709776 32457 786096 473537 340357 123986 218042 59148 431364 159599 169388 51088 499419 495088 52160 483836 53372 405718 342457 56...
output:
no no no no yes no no no no yes no no no no no no yes no yes no no no no no no yes no yes no no no no yes no yes no no yes no no yes no no no no no no no no no no no no no yes no yes no no yes yes no no no no no no no no no no yes no no yes no no no no no no no no no no no no no no no yes no no no n...
result:
ok 276 lines
Test #32:
score: 0
Accepted
time: 0ms
memory: 1320kb
input:
10 177925 228 54875 88097 9458 96183 423142 7144 125819 510966 106 26106 931540 3783 51728 19741 9327 23805 711170 8284 37144 8806 2242 9139 301541 8470 56032 439870 6799 116749 377 718340 141135 260880 624930 263452 384824 192247 266150 351840 425610 313056 520775 384494 133075 273332 671550 652200...
output:
no no yes no yes no yes no no no no yes no no no no no no no no no no no no no no no no no no no yes no yes no yes no no yes no no no no yes no no yes yes yes no no no no yes no no no yes yes yes no yes yes no no no no no no no yes no yes yes yes yes no yes yes no no no no yes no no yes no yes no ye...
result:
ok 377 lines
Test #33:
score: 0
Accepted
time: 0ms
memory: 1324kb
input:
10 680511 8416 72678 599653 3748 153608 80906 3691 6287 2007 2715 63382 642959 5501 117896 846413 9929 63523 32994 7082 151910 15954 5420 53638 263250 5328 50286 70350 9586 59018 323 682752 365681 450688 553974 191072 118368 157824 143304 186255 122082 382144 59184 87130 364562 237864 561974 87086 3...
output:
no yes no no no no yes yes yes no no yes yes no no no no no no no yes no no no no no no yes no no yes no yes no no no no yes yes no no yes no no no no no yes yes yes no no yes no yes yes no yes yes no no yes no no no no no yes no yes no no no yes no yes yes no no no no no yes yes yes no yes no no ye...
result:
ok 323 lines