QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#746679 | #62. Examination | Shumomo | 0 | 139ms | 12360kb | C++14 | 1.8kb | 2024-11-14 15:15:42 | 2024-11-14 15:15:42 |
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-1;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-1;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=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].a++;
x[i].b++;
x[i].c++;
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: 0
Wrong Answer
Test #1:
score: 2
Accepted
time: 1ms
memory: 7992kb
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: 8048kb
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: 0ms
memory: 7872kb
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: 8052kb
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: 7864kb
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: 1ms
memory: 8056kb
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: 5ms
memory: 7952kb
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: 5ms
memory: 7960kb
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: 5ms
memory: 10068kb
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: 0
Wrong Answer
time: 4ms
memory: 8008kb
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:
428 147 801 525 766 100 21 966 154 719 599 771 1667 1440 235 473 724 960 590 126 1112 16 535 423 575 836 119 469 976 35 335 966 641 1646 236 103 14 996 276 567 2241 1251 280 375 1299 47 222 331 13 363 185 49 355 587 1566 321 1928 67 814 368 473 232 1768 959 99 175 1470 0 388 255 754 131 598 1248 646...
result:
wrong answer 1st lines differ - expected: '381', found: '428'
Subtask #2:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 139ms
memory: 12360kb
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:
3392 12465 20237 13566 11736 28515 4108 33065 27852 26019 23511 12296 30617 230 20831 1461 3465 17020 36047 23197 69812 24530 13443 8259 24435 733 10412 20119 15898 75646 27340 73796 46246 61350 520 59415 6149 798 2836 4629 14775 40982 38232 7313 39010 14774 27554 20183 82759 35655 3811 29324 5084 6...
result:
wrong answer 4th lines differ - expected: '13565', found: '13566'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%