QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#746796 | #62. Examination | Shumomo | 2 | 26ms | 10088kb | C++14 | 1.8kb | 2024-11-14 15:34:43 | 2024-11-14 15:34:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct node{
int a,b,c,d;
bool operator <(const node &aa)const{
return a<aa.a||(a==aa.a&&d>aa.d);
}
}x[200009],y[200009];
int n,q,f[200009],ans[200009],v[200009];
void solve(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
solve(l,mid);
solve(mid+1,r);
int nw=r,ll=mid,rr=r;
while(ll>=l&&rr>mid){
if(x[ll].b>x[rr].b){
if(x[ll].d>0){
for(int i=x[ll].c;i;i-=(i&(-i)))ans[x[ll].d]+=v[i];
}
y[nw--]=x[ll--];
}
else {
if(x[rr].d<0)for(int i=x[rr].c;i<=n+q;i+=(i&(-i)))v[i]++;
y[nw--]=x[rr--];
}
}
while(ll>=l){
if(x[ll].d>0){
for(int i=x[ll].c;i;i-=(i&(-i)))ans[x[ll].d]+=v[i];
}
y[nw--]=x[ll--];
}
while(rr>mid){
if(x[rr].d<0)for(int i=x[rr].c;i<=n+q;i+=(i&(-i)))v[i]++;
y[nw--]=x[rr--];
}
for(int i=mid+1;i<=r;i++){
if(x[i].d<0)for(int j=x[i].c;j<=n+q;j+=(j&(-j)))v[j]--;
}
for(int i=1;i<=n+q;i++)assert(!v[i]);
for(int i=l;i<=r;i++){
x[i]=y[i];
}
return;
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i].a,&x[i].b);
x[i].c=x[i].a+x[i].b;
x[i].d=-i;
f[i]=x[i].c;
}
for(int i=n+1;i<=n+q;i++){
scanf("%d%d%d",&x[i].a,&x[i].b,&x[i].c);
x[i].d=i-n;
f[i]=x[i].c;
}
sort(f+1,f+n+q+1);
for(int i=1;i<=n+q;i++){
x[i].c=lower_bound(f+1,f+n+q+1,x[i].c)-f;
x[i].c=n+q+1-x[i].c;
}
sort(x+1,x+n+q+1);
solve(1,n+q);
for(int i=1;i<=q;i++){
printf("%d\n",ans[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 2
Accepted
Test #1:
score: 2
Accepted
time: 1ms
memory: 8004kb
input:
10 10 28 2 78 81 39 79 61 31 36 99 90 5 20 55 91 4 48 19 80 7 52 43 78 64 65 171 34 68 124 37 80 161 53 19 123 49 58 109 95 46 30 45 48 60 47 13 54 64 30 144
output:
1 0 2 0 1 1 0 1 3 1
result:
ok 10 lines
Test #2:
score: 2
Accepted
time: 1ms
memory: 10088kb
input:
10 10 6 67 36 99 13 45 100 87 60 72 55 41 62 92 55 39 90 22 0 99 34 89 79 17 17 23 60 26 171 29 88 190 32 71 98 20 29 192 50 7 34 14 21 139 54 35 103 86 91 1
output:
2 7 1 0 4 0 6 2 3 0
result:
ok 10 lines
Test #3:
score: 2
Accepted
time: 1ms
memory: 7876kb
input:
10 10 67 72 94 99 34 22 1 71 68 18 90 94 29 44 98 61 46 9 94 76 73 36 11 30 26 75 5 85 112 38 35 111 39 72 143 6 64 130 31 24 134 82 86 188 80 20 151 91 32 62
output:
4 5 2 5 3 4 5 1 4 3
result:
ok 10 lines
Test #4:
score: 2
Accepted
time: 1ms
memory: 7940kb
input:
10 10 667489048 282547819 694873877 525794923 605957229 147658688 928289876 455560133 465507205 531350815 397977066 913356070 351069660 834164613 611261253 238522918 683770744 737447844 351350094 473152918 514777487 599392520 569824365 137189600 455145855 1628925058 608994260 433029864 1934471803 80...
output:
1 0 0 1 2 0 10 0 1 0
result:
ok 10 lines
Test #5:
score: 2
Accepted
time: 1ms
memory: 9908kb
input:
10 10 263981199 52332634 326795173 857652684 184061837 846545137 39542400 348620078 96871071 314776708 19327149 702608210 486997547 362493836 734600837 228406106 676322287 184313447 205910594 985010975 928597138 172342418 665625750 340192959 922085230 1825805421 805685495 219541540 475070350 4658221...
output:
0 0 0 3 0 0 3 0 0 0
result:
ok 10 lines
Test #6:
score: 2
Accepted
time: 0ms
memory: 8004kb
input:
10 10 938568749 622216614 473949650 794427283 821003445 932759572 521639872 980300286 221194869 486910867 809253866 513217132 566374168 282501808 288139033 402357178 916473963 145958981 592255402 968995324 113069862 909714805 1855286879 572813519 935368048 360790753 835912982 28401519 1522137034 943...
output:
0 1 1 0 2 0 7 0 2 9
result:
ok 10 lines
Test #7:
score: 2
Accepted
time: 26ms
memory: 7940kb
input:
3000 3000 40944019 692692877 645016109 145199524 568250169 363353983 626494606 558783087 161612818 101360006 34139264 867093007 708172540 84650861 45799594 79255002 364942843 522551858 327755779 907461393 429041284 748255933 912770818 886733119 19971581 580290777 717292638 606814849 840433536 332990...
output:
1602 171 930 467 30 1316 125 475 883 1105 135 427 478 89 840 1466 3 0 591 34 368 4 936 590 246 270 1168 18 79 9 303 533 19 491 163 287 1350 445 23 151 2006 184 1233 11 175 1348 515 229 717 889 60 37 4 273 324 81 4 471 1275 11 207 444 1214 232 85 686 182 709 513 207 1451 418 2041 729 3 871 466 51 198...
result:
ok 3000 lines
Test #8:
score: 2
Accepted
time: 22ms
memory: 8004kb
input:
3000 3000 907627167 686752093 462625412 852663910 500152795 14286796 910681862 200991087 109311919 35030354 156913954 564324169 181028206 930471944 686123971 163012566 732920495 314853990 910305661 51938497 868182462 323159996 777537241 919935911 714475342 334517770 927209935 435695974 747799830 888...
output:
70 62 456 163 1557 359 169 428 194 70 364 593 296 99 4 166 435 632 1 1315 21 137 72 375 111 674 491 1398 96 339 280 1 211 94 890 0 757 106 428 478 637 133 357 1009 422 706 224 111 231 677 21 990 1361 113 682 393 6 186 295 288 28 1586 82 186 21 92 64 416 127 453 174 500 8 374 257 10 195 441 213 2292 ...
result:
ok 3000 lines
Test #9:
score: 2
Accepted
time: 22ms
memory: 10076kb
input:
3000 3000 334978095 565095638 78003245 739839219 211920625 294829 835598279 911193731 640309078 196393030 930111636 843404908 272429756 299106119 421405869 635269635 422157528 163791651 220891615 341620330 768573478 656606438 898559946 184092507 551655307 968524071 495019662 642996661 48050546 23559...
output:
305 17 1801 760 1981 737 261 136 282 495 8 58 117 102 1053 922 6 872 1305 1011 443 286 458 14 22 72 150 1341 537 403 4 885 626 1328 39 442 324 0 1456 210 35 539 1153 278 162 961 55 4 790 90 3 957 155 891 396 2412 63 0 1018 2211 176 432 152 33 440 230 238 139 314 69 311 3 936 136 730 1366 106 440 823...
result:
ok 3000 lines
Test #10:
score: 2
Accepted
time: 25ms
memory: 7888kb
input:
3000 3000 670721945 0 918363246 4 530498664 8 151236440 1 551302032 5 744761966 3 677885226 8 425828663 4 806962929 7 86226431 3 553505514 6 229344072 1 495287254 4 742717671 8 107255479 2 872256841 10 891288366 1 344265685 9 837502103 4 146091952 6 611328716 3 592876764 10 641850002 6 898856374 8 4...
output:
381 125 529 344 665 51 17 830 103 605 395 668 1507 1322 189 387 590 828 510 84 960 14 491 377 520 770 101 369 839 31 217 830 524 1477 205 87 12 996 235 521 2051 1117 238 178 1127 47 222 281 11 363 158 34 302 587 1408 287 1768 67 680 327 400 118 1591 804 84 162 1278 0 258 173 655 101 502 1012 565 269...
result:
ok 3000 lines
Test #11:
score: 2
Accepted
time: 22ms
memory: 7984kb
input:
3000 3000 8 375396159 8 368119562 1 575071003 0 713872346 8 587408547 7 78445830 3 900615065 0 97512137 4 875603716 3 187655071 3 321929391 4 341544316 5 427645484 5 264570850 8 560506150 8 208439714 3 264016831 2 461763351 1 831864441 5 487169227 3 762640963 4 222377711 10 632245214 7 14464390 9 40...
output:
1504 128 221 73 789 375 3 1103 2391 155 307 592 149 25 106 112 393 461 842 403 752 119 51 896 392 631 71 93 1182 753 334 2273 624 530 488 1465 13 5 1289 3 162 1744 511 164 612 435 801 1720 1017 855 1291 952 1096 593 299 31 158 219 420 37 66 991 193 2231 117 1357 388 363 18 1443 1054 486 107 72 32 39...
result:
ok 3000 lines
Test #12:
score: 2
Accepted
time: 24ms
memory: 7968kb
input:
3000 3000 8 9 5 2 9 2 6 5 3 3 9 10 6 10 5 1 4 9 4 3 0 9 4 3 0 4 10 3 2 2 8 7 10 5 4 0 9 9 7 9 2 2 10 3 1 2 10 5 7 2 7 8 0 10 4 3 2 10 10 1 5 9 3 5 5 4 7 1 4 4 7 6 7 2 6 4 9 7 2 9 3 2 0 10 3 6 6 7 8 0 5 10 0 2 6 3 0 6 2 3 4 2 5 3 10 6 9 0 5 5 3 10 5 0 1 7 9 9 0 7 7 3 8 9 2 3 3 1 8 10 4 7 10 10 10 3 0...
output:
1325 19 361 137 168 434 170 57 896 360 168 950 324 2158 338 510 116 215 1550 1163 132 896 2054 94 137 359 259 297 1973 1061 199 1475 510 365 343 225 804 235 235 279 19 281 365 236 894 1554 1619 116 1163 2443 1964 510 484 784 294 91 660 132 739 983 1087 195 1319 273 583 33 1932 876 146 365 371 203 59...
result:
ok 3000 lines
Test #13:
score: 2
Accepted
time: 26ms
memory: 8012kb
input:
3000 3000 877137497 911480796 105327974 808804262 727937300 637853442 718031794 765195805 838206925 484239980 607467843 605792963 38697321 332194606 273988991 323047106 798562928 435509930 372308224 443534703 707117309 487932296 211775547 761591409 77454450 882287786 277784786 263090911 819288578 17...
output:
1524 1296 1606 226 1445 158 382 435 13 182 1983 223 81 1832 469 1188 375 353 617 882 244 939 819 612 448 355 458 296 1024 301 855 732 1256 553 1143 755 978 1995 1263 1652 2018 239 38 1472 916 1172 662 1021 366 1480 136 716 1246 420 1549 24 257 831 143 164 466 1551 1476 499 1488 937 511 85 652 134 85...
result:
ok 3000 lines
Test #14:
score: 2
Accepted
time: 25ms
memory: 7964kb
input:
3000 3000 10427381 302072811 305423535 159511618 389241521 972714841 87239050 654013994 553105278 55046924 721109311 612092521 522048131 811507269 616929981 759331556 694803970 82587802 55757168 4610834 227644683 145826047 767743895 527337462 664853723 570569400 225987816 848995384 922146032 1350592...
output:
149 135 169 182 111 161 1515 1355 1736 2239 249 682 1721 1992 2006 1036 652 1810 577 810 471 1122 513 107 64 1907 1482 1707 531 972 679 197 34 382 7 107 623 573 132 767 61 106 60 1957 69 34 103 456 4 896 1516 1571 570 1885 573 1237 1652 433 1428 1 133 31 761 31 2282 591 1418 2078 102 21 212 1090 687...
result:
ok 3000 lines
Test #15:
score: 2
Accepted
time: 25ms
memory: 8060kb
input:
3000 3000 81888039 43067130 107207950 11840118 12213117 1564707 591852272 88838686 961663048 516561908 168803247 844631606 873195252 827482721 743609372 619362988 538294586 82184626 144127316 243409881 211682136 271003480 663591068 168473714 654369343 16498796 591919034 700712174 385773732 618206738...
output:
128 125 1701 799 67 1725 1166 370 80 481 533 606 82 8 2273 272 2646 637 955 661 484 2418 63 47 269 162 1864 364 873 135 947 401 126 1380 56 54 2756 279 352 327 633 1453 114 319 1142 219 5 1100 495 88 13 1948 37 773 823 284 1012 612 195 248 1585 1517 37 159 1940 768 482 419 659 245 1599 923 879 99 47...
result:
ok 3000 lines
Test #16:
score: 2
Accepted
time: 25ms
memory: 8104kb
input:
3000 3000 0 265577685 0 279712461 0 865961338 0 715526160 0 152109041 0 720516447 0 663839583 0 572363102 0 15684570 0 774105531 0 355480679 0 318103883 0 809487980 0 566618853 0 399560845 0 428122875 0 406123722 0 227690500 0 306745648 0 787880089 0 156872708 0 469927843 0 869358593 0 484045893 0 4...
output:
216 312 0 4 0 2580 1282 0 0 2331 0 0 1108 0 710 1405 0 2129 0 0 1820 0 0 1698 0 1215 1389 0 0 2892 2456 2856 0 0 111 1849 205 0 795 0 0 0 2288 849 1432 927 0 0 227 1335 0 1565 17 398 1512 282 1611 0 2268 2894 0 337 0 277 2501 0 2182 0 21 0 1568 0 1706 1102 0 454 0 2457 0 0 0 0 0 0 0 1993 0 78 0 0 0 ...
result:
ok 3000 lines
Test #17:
score: 2
Accepted
time: 25ms
memory: 8076kb
input:
3000 3000 905574076 0 62086925 0 984401157 0 900477115 0 688562084 0 607520732 0 679335141 0 4786510 0 595168939 0 16199355 0 932151269 0 333912126 0 772707530 0 544868665 0 863264108 0 492456951 0 971680943 0 930894040 0 405136186 0 728899221 0 800538513 0 145763793 0 544013589 0 250213891 0 317696...
output:
0 0 0 0 0 411 811 625 2171 0 0 0 1283 992 0 0 0 41 0 0 10 843 672 876 876 1217 2327 0 0 0 0 77 0 0 0 0 888 1891 563 0 1508 1284 1618 546 0 0 1391 0 688 270 989 106 0 0 1711 1461 0 1923 0 2260 435 0 0 1759 1353 0 0 843 1301 0 547 0 373 0 823 0 1864 492 0 0 0 0 1058 0 0 0 0 682 0 186 1198 0 544 1200 2...
result:
ok 3000 lines
Test #18:
score: 2
Accepted
time: 23ms
memory: 8056kb
input:
3000 3000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 3000 0 0 0 3000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3000 0 3000 3000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 3000 lines
Subtask #2:
score: 0
Time Limit Exceeded
Test #19:
score: 0
Time Limit Exceeded
input:
100000 100000 26753 11234 32815 62591 34318 93262 77179 57605 88208 33327 48449 99060 42403 58561 85715 7001 2418 90938 77409 6957 546 83283 53957 8374 49470 1483 65866 64950 4269 8745 19041 85833 22344 90706 92926 35603 54697 75311 72601 66401 77598 8193 3751 54202 32710 5877 23835 38264 34381 3338...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%