QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#19002 | #1877. Matryoshka Dolls | alan__zhao | TL | 3895ms | 16180kb | C++11 | 1.9kb | 2022-01-27 18:18:23 | 2022-05-06 03:32:10 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
#define Debug(...) fprintf(stderr,__VA_ARGS__)
typedef long long ll;
const int N=5e5+5;
int Abs(int x){return x<0?-x:x;}
int n,m,a[N],bsiz,pos[N];
struct Fenwick{
int t[N]={};
void Add(int p,int k){for(;p<=n;p+=p&-p) t[p]+=k;}
int QSum(int p){int res=0;for(;p;p-=p&-p) res+=t[p]; return res;}
int QVal(int k){
int p=0,s=0;
Dec(i,20,0){
if(p+(1<<i)>n||s+t[p+(1<<i)]>=k) continue;
p+=1<<i,s+=t[p];
}
return p+1;
}
int QPre(int p){
int s=QSum(p-1);
return s?QVal(s):0;
}
int QNext(int p){return QVal(QSum(p)+1);}
};
namespace Mo{
struct Query{
int l,r,i;
bool operator<(const Query &x){
if(l/bsiz!=x.l/bsiz) return l<x.l;
return ((l/bsiz)&1)?(r<x.r):(r>x.r);
}
}q[N];
ll cur;Fenwick bit;
void Oper(int x,int k){
int pre=bit.QPre(x),nxt=bit.QNext(x);
bit.Add(x,k);
if(!pre&&nxt==n+1) return;
if(nxt!=n+1) cur+=k*Abs(pos[nxt]-pos[x]);
if(pre) cur+=k*Abs(pos[pre]-pos[x]);
if(nxt!=n+1&&pre) cur+=-k*Abs(pos[nxt]-pos[pre]);
}
void Add(int x){Oper(x,1);}
void Del(int x){Oper(x,-1);}
ll ans[N];
void Solve(){
bsiz=max(1.,double(n)/sqrt(m));
For(i,1,m) cin>>q[i].l>>q[i].r,q[i].i=i;
sort(q+1,q+m+1);
for(int i=1,l=1,r=0;i<=m;++i){
if(q[i].l==q[i].r){
ans[q[i].i]=0;continue;
}
while(l>q[i].l) Add(a[--l]);
while(r<q[i].r) Add(a[++r]);
while(l<q[i].l) Del(a[l++]);
while(r>q[i].r) Del(a[r--]);
ans[q[i].i]=cur;
}
For(i,1,m) cout<<ans[i]<<'\n';
}
}
int main(){
// freopen("rrads.in","r",stdin);
// freopen("rrads.out","w",stdout);
#ifndef zyz
ios::sync_with_stdio(false),cin.tie(nullptr);
#endif
cin>>n>>m;
For(i,1,n) cin>>a[i],pos[a[i]]=i;
Mo::Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11848kb
input:
5 5 1 5 2 4 3 1 5 1 4 1 3 1 2 1 1
output:
7 5 3 1 0
result:
ok 5 number(s): "7 5 3 1 0"
Test #2:
score: 0
Accepted
time: 4ms
memory: 9888kb
input:
1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 16ms
memory: 11876kb
input:
100000 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 ...
output:
4999950000
result:
ok 1 number(s): "4999950000"
Test #4:
score: 0
Accepted
time: 1ms
memory: 11812kb
input:
20 1 12 8 13 10 18 14 1 19 5 16 15 9 17 20 6 2 11 4 3 7 9 18
output:
36
result:
ok 1 number(s): "36"
Test #5:
score: 0
Accepted
time: 0ms
memory: 11932kb
input:
20 10 5 16 11 7 19 8 12 13 17 18 6 1 14 3 4 2 15 20 10 9 7 11 7 13 7 17 11 15 1 7 4 6 1 5 6 14 3 5 9 9
output:
7 16 34 9 20 3 8 22 3 0
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 3ms
memory: 11936kb
input:
20 50 7 3 13 8 9 18 1 15 12 10 20 11 17 16 2 19 5 4 6 14 3 6 5 15 11 20 10 18 9 20 3 17 13 20 16 17 3 20 4 17 15 18 5 19 3 14 8 20 2 20 1 4 15 19 16 20 5 13 14 17 4 10 6 16 8 16 1 12 4 9 11 15 4 20 8 11 3 16 7 7 3 11 3 7 4 4 5 12 6 20 3 14 6 19 6 19 2 14 2 12 5 6 4 6 8 15 10 19 4 14 1 16 1 20 2 13 3...
output:
6 48 36 24 46 74 17 1 104 64 5 68 44 58 130 5 9 8 30 7 13 48 26 38 11 8 92 5 70 0 28 9 0 20 80 44 58 58 48 36 1 2 20 28 34 76 136 46 1 28
result:
ok 50 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 11808kb
input:
20 100 4 13 20 8 1 18 19 9 17 5 12 7 11 16 6 3 15 10 14 2 4 19 1 6 6 19 4 6 2 17 1 5 11 13 1 15 9 17 9 15 7 20 3 19 10 19 1 10 11 17 10 17 2 18 17 20 12 19 1 3 5 17 7 13 6 18 10 20 1 6 2 17 5 9 4 13 11 13 2 20 7 13 12 17 5 19 17 20 11 19 3 15 3 5 5 11 1 17 10 15 16 20 1 6 2 19 4 12 5 18 9 17 3 6 12 ...
output:
76 16 57 3 84 10 3 74 31 19 59 80 40 44 16 26 94 5 26 2 54 17 53 44 16 84 8 32 3 106 17 12 68 5 30 48 2 16 102 14 9 16 98 28 64 31 6 1 54 20 26 31 74 5 26 3 66 32 36 59 1 26 6 33 35 5 57 1 1 57 24 6 10 68 36 41 34 0 12 8 11 2 62 12 41 10 5 25 0 60 0 44 25 12 8 2 16 36 8 1
result:
ok 100 numbers
Test #8:
score: 0
Accepted
time: 2ms
memory: 11840kb
input:
20 228 7 3 17 10 16 11 19 5 1 13 20 18 14 2 8 4 6 9 12 15 7 20 2 20 10 13 14 19 1 9 12 20 17 19 9 20 10 12 14 17 4 15 7 16 5 12 13 16 16 18 7 18 1 11 7 17 2 20 6 8 9 17 12 18 7 18 3 4 7 13 1 4 6 12 6 10 3 17 3 4 5 14 7 13 9 20 6 20 2 4 14 17 17 20 1 7 19 20 4 20 14 15 12 16 4 6 4 15 10 11 2 16 2 20 ...
output:
66 136 5 9 32 30 2 42 3 5 62 40 28 5 2 50 44 44 136 3 20 14 50 1 16 5 18 10 74 1 44 16 42 90 3 5 3 13 1 108 1 6 3 62 1 94 136 3 14 42 3 80 26 6 54 7 26 26 31 1 74 38 15 14 52 26 14 6 4 7 3 2 70 13 2 44 6 76 26 90 1 66 108 0 28 16 132 18 7 3 14 48 7 15 1 8 9 22 9 18 36 5 70 44 42 3 1 42 0 3 3 8 3 62 ...
result:
ok 228 numbers
Test #9:
score: 0
Accepted
time: 5ms
memory: 11860kb
input:
20 322 3 11 4 1 9 19 7 12 5 17 8 15 10 18 13 2 20 16 14 6 8 14 6 6 3 17 3 16 9 18 7 17 12 13 4 14 12 18 6 13 8 9 3 17 7 20 12 16 10 15 12 16 12 14 16 19 6 7 18 20 6 16 7 14 5 19 12 13 3 14 10 15 11 18 12 20 8 9 1 13 17 18 1 18 4 19 4 9 5 19 4 5 1 2 10 17 11 19 7 14 15 20 20 20 4 7 12 15 7 17 3 13 7 ...
output:
19 0 91 80 37 39 1 48 21 23 1 91 81 10 13 10 3 5 1 2 44 23 87 1 50 13 25 37 1 58 1 119 99 14 87 1 1 21 33 23 15 0 6 7 39 42 36 1 91 3 107 25 1 44 1 0 10 7 1 1 55 3 10 2 34 91 1 51 26 25 75 1 1 18 79 13 1 80 21 16 5 3 0 18 3 7 63 63 66 3 0 5 17 0 21 10 1 3 5 1 6 35 41 29 59 43 21 0 45 3 6 75 1 103 0 ...
result:
ok 322 numbers
Test #10:
score: 0
Accepted
time: 3ms
memory: 11792kb
input:
20 1000 16 6 17 1 12 11 5 8 10 19 4 18 2 9 14 7 15 3 20 13 1 6 8 9 9 11 5 18 3 20 2 9 17 18 12 12 12 20 5 17 1 8 10 10 2 9 17 19 1 7 7 15 12 19 2 7 9 14 2 14 1 4 15 17 11 19 2 5 3 12 11 14 11 14 13 17 7 8 9 18 2 11 8 11 1 4 4 8 12 13 12 19 7 16 12 16 11 15 5 9 5 18 2 19 11 15 1 15 4 20 4 9 5 14 5 19...
output:
13 1 3 67 113 21 1 0 34 57 23 0 21 3 19 29 24 15 15 54 5 3 34 7 30 7 7 8 1 39 36 5 5 7 1 24 45 9 9 6 67 113 9 78 95 9 31 76 34 25 78 9 7 9 3 6 21 5 78 55 70 13 51 5 29 9 7 1 14 9 1 3 13 3 94 39 7 4 104 44 17 24 29 85 26 9 49 67 40 5 3 7 65 0 54 76 14 67 7 18 37 7 19 1 5 11 27 21 30 21 7 95 23 15 40 ...
result:
ok 1000 numbers
Test #11:
score: 0
Accepted
time: 3ms
memory: 11820kb
input:
20 1000 16 8 20 2 5 9 14 7 19 3 13 1 6 18 10 4 15 17 12 11 9 19 12 12 12 19 15 15 6 17 9 16 1 10 4 19 10 13 11 18 2 7 12 17 18 19 4 15 3 18 3 17 5 11 14 17 4 16 3 13 10 10 12 20 1 1 4 8 3 11 8 15 6 7 9 12 1 16 12 20 2 9 8 9 8 9 8 20 17 18 15 20 11 20 1 3 8 10 2 6 8 18 4 12 7 12 3 18 5 14 14 15 6 10 ...
output:
41 0 20 0 53 25 45 91 7 24 13 14 1 63 89 87 21 6 75 51 0 22 0 7 33 29 1 5 101 22 23 1 1 53 1 10 34 3 3 11 43 35 13 89 43 1 7 20 6 33 6 2 1 15 51 41 13 29 1 4 10 51 13 1 16 10 45 19 1 11 3 71 15 22 15 35 87 87 129 23 61 2 33 7 51 0 89 43 3 1 7 71 8 75 7 16 105 19 9 14 43 29 35 33 23 20 29 5 2 3 16 4 ...
result:
ok 1000 numbers
Test #12:
score: 0
Accepted
time: 3ms
memory: 11748kb
input:
20 1000 7 16 3 15 5 6 10 20 19 2 13 1 11 4 8 18 12 17 14 9 9 20 17 19 1 13 5 19 18 18 6 8 6 14 3 16 6 16 12 17 9 11 9 20 7 20 3 18 10 13 2 8 6 17 5 7 7 15 3 8 11 13 13 18 6 15 8 18 5 10 6 8 13 20 6 7 10 13 6 20 10 12 12 18 9 12 4 12 16 18 2 5 1 11 3 10 13 18 6 20 2 4 3 8 13 20 17 20 3 13 1 10 1 15 1...
output:
47 3 48 68 0 2 26 82 52 10 3 47 60 94 7 15 60 2 26 11 3 10 42 36 10 2 22 1 7 76 3 12 5 26 3 5 42 20 10 76 3 11 22 6 34 34 82 4 3 11 12 13 1 2 5 1 0 24 16 124 1 9 5 13 90 3 26 6 94 98 86 3 5 14 37 28 38 3 1 30 98 4 0 60 42 0 1 20 6 16 12 1 1 10 11 18 98 24 16 1 4 80 16 26 28 1 124 6 1 40 14 3 16 10 3...
result:
ok 1000 numbers
Test #13:
score: 0
Accepted
time: 5ms
memory: 11752kb
input:
20 1337 10 3 6 8 7 15 4 5 9 19 17 13 1 18 12 16 20 2 11 14 10 14 4 5 9 11 7 14 2 8 7 18 11 18 9 12 2 6 8 15 11 18 12 16 19 19 8 19 12 16 4 11 2 18 1 6 15 19 2 12 4 9 3 5 16 20 10 14 3 9 10 10 7 17 6 11 8 10 3 4 6 18 7 12 1 15 7 16 16 17 3 16 6 12 4 15 10 17 13 19 4 20 18 19 13 14 3 16 8 10 3 16 1 14...
output:
9 1 3 19 16 50 26 5 6 23 26 11 0 56 11 19 84 12 7 34 13 3 7 9 17 0 40 11 2 1 62 7 73 33 1 57 17 43 28 16 94 1 1 57 2 57 67 74 5 5 24 60 4 76 52 3 1 15 9 16 1 19 15 5 2 35 60 5 35 92 22 3 1 0 3 9 6 6 6 73 54 36 9 14 11 17 0 108 73 67 83 4 44 41 14 83 0 3 1 17 64 4 17 17 45 11 3 15 50 23 4 1 30 17 74 ...
result:
ok 1337 numbers
Test #14:
score: 0
Accepted
time: 8ms
memory: 11824kb
input:
1000 1000 40 954 881 24 748 110 805 978 860 472 882 621 530 586 488 928 150 443 553 402 177 702 871 214 778 7 489 874 812 754 90 806 206 60 283 243 416 720 650 539 763 588 570 114 658 396 19 970 372 743 587 885 527 296 3 900 313 968 772 280 691 349 37 178 714 49 122 823 143 632 662 387 88 176 400 63...
output:
91858 15668 172586 11352 13480 1 8256 24603 28782 1468 53656 189822 185548 14226 107100 70306 22628 158766 20021 10226 50340 45240 14040 108754 64658 83894 78280 59 145572 421 73592 583 96644 154438 95660 132514 45756 64674 4054 53331 32650 40791 2868 264 53 49416 38470 183908 51910 112924 13670 139...
result:
ok 1000 numbers
Test #15:
score: 0
Accepted
time: 4ms
memory: 11752kb
input:
1000 1000 266 949 588 125 665 728 319 483 107 605 86 142 593 228 829 702 298 808 615 575 467 3 548 345 492 859 848 685 265 945 773 440 698 71 743 630 311 834 671 544 927 906 422 614 367 989 923 210 44 856 638 98 636 726 609 76 113 796 565 750 103 196 668 589 278 264 784 998 794 105 354 600 369 931 2...
output:
344 18157 32 669 175 79412 1280 28341 20245 9269 33207 4268 643 5859 40615 71451 25640 32121 65902 2432 11292 65986 19331 226 20819 41463 30009 74575 22 21597 96801 81093 2388 10777 22657 1256 81865 1073 21 166635 51935 33323 55761 489 18242 44795 12578 55349 186681 159317 3224 5235 41753 136129 589...
result:
ok 1000 numbers
Test #16:
score: 0
Accepted
time: 8ms
memory: 11684kb
input:
1000 1000 39 785 629 568 287 13 150 901 702 805 204 362 575 339 843 26 380 291 927 181 9 278 662 876 674 129 794 809 866 442 709 966 644 737 978 283 507 627 525 460 279 375 389 454 369 27 603 121 255 230 528 727 777 589 942 923 145 266 443 249 697 789 812 536 586 391 93 833 267 202 505 956 744 57 39...
output:
58022 164646 252248 24113 712 27872 108362 40237 224150 17438 138258 360 5699 239 15925 205084 2594 55280 6181 71954 25072 79116 10618 34263 373 53596 22330 194978 46786 10422 145746 13962 4838 8935 1291 14694 10340 55920 5263 11863 153 50 65316 2623 9454 151682 242372 4079 6 534 12356 15813 12845 1...
result:
ok 1000 numbers
Test #17:
score: 0
Accepted
time: 8ms
memory: 11816kb
input:
1000 1000 556 686 702 301 252 724 158 296 86 834 162 884 890 448 815 844 974 369 237 411 8 868 353 299 578 527 166 797 141 498 775 997 5 479 732 902 246 244 624 918 376 718 680 990 441 593 234 898 762 339 433 689 233 579 394 938 725 897 455 110 513 362 417 821 477 204 24 747 982 891 925 870 754 271 ...
output:
37802 23905 294066 33720 74794 166792 9370 3169 164940 121220 13 5527 356 113886 53536 153872 29238 264 9289 117314 89842 162068 279608 2635 106 22107 28389 26198 6332 51546 949 15872 307 81238 114314 163594 146270 15078 1009 147878 15076 3283 753 4057 1065 7694 29161 82 1097 13822 57 136566 21204 6...
result:
ok 1000 numbers
Test #18:
score: 0
Accepted
time: 8ms
memory: 11792kb
input:
1000 1000 487 188 387 532 411 790 570 219 22 672 347 510 805 258 736 892 776 840 400 104 227 843 557 407 670 208 574 350 440 163 335 895 369 398 502 46 19 380 18 470 395 293 537 423 235 51 260 538 361 612 905 270 385 645 88 296 733 316 229 847 851 751 978 76 923 699 677 332 841 20 657 15 703 565 169...
output:
4676 12529 10123 121945 51016 50950 35034 9346 20339 11943 900 45 10899 40782 9850 220350 57477 9152 45926 8477 24860 9549 60180 27213 4 14988 241070 27674 14923 126190 67108 42606 98 8136 12274 67838 86 67736 68234 62756 57287 15743 1384 19231 142330 101952 636 266 167380 180794 13093 157492 119534...
result:
ok 1000 numbers
Test #19:
score: 0
Accepted
time: 2ms
memory: 9852kb
input:
1000 1000 832 212 419 284 882 369 312 437 496 937 652 363 659 840 791 572 730 772 416 63 929 302 494 24 61 329 163 241 542 316 341 41 388 164 525 123 472 871 540 222 150 888 82 926 192 249 252 861 761 628 326 465 909 116 842 457 578 487 17 600 998 678 686 187 538 102 243 92 960 788 332 373 923 546 7...
output:
22850 1404 56350 99385 8530 111263 112429 110327 30307 84285 175189 8278 36519 15670 22393 23394 49964 70090 18303 12420 17887 64227 128351 4461 88687 36231 124735 197623 190541 190695 19010 1298 256333 12395 39703 75101 5953 2030 6329 21387 87957 19535 158807 1888 1385 6442 153793 23755 460 17138 2...
result:
ok 1000 numbers
Test #20:
score: 0
Accepted
time: 2ms
memory: 9644kb
input:
1000 1000 985 117 995 842 388 526 509 668 773 738 926 747 166 466 114 983 597 89 124 230 818 441 178 211 43 325 858 584 843 456 240 486 674 313 315 719 550 400 323 9 264 29 414 277 96 734 238 152 554 207 170 363 428 488 537 492 596 618 778 279 721 735 222 941 236 736 866 63 485 258 540 110 434 856 3...
output:
78364 52364 127886 984 1555 36880 292085 65 9337 54109 2194 169387 15385 162293 149983 588 148333 176831 62758 24026 65099 160561 21377 55331 100 11041 74818 78045 2443 19645 22600 89582 49978 235011 604 221613 110101 168307 126573 65932 4240 240537 28833 216487 15865 121457 5327 70546 13277 5013 16...
result:
ok 1000 numbers
Test #21:
score: 0
Accepted
time: 3ms
memory: 11824kb
input:
1000 1000 585 437 432 207 862 723 368 485 692 687 607 385 612 981 182 405 162 912 502 573 765 963 801 104 451 440 718 238 512 817 246 748 516 184 250 105 550 902 174 760 242 285 237 14 764 997 617 533 777 519 675 968 154 462 987 172 126 740 436 549 133 706 12 962 587 209 887 508 903 328 76 653 298 3...
output:
428 6340 1658 4990 27629 21897 152237 190416 43389 33458 365 64021 18 105531 175631 88041 71001 12446 4520 109267 139681 122035 0 28288 64555 10643 1994 53 109231 120 43461 67 190039 237 9856 547 26351 38487 13923 43427 93 72701 170 9482 12064 119105 9575 649 133545 38902 19291 28461 69723 724 648 1...
result:
ok 1000 numbers
Test #22:
score: 0
Accepted
time: 3ms
memory: 11800kb
input:
1000 1000 535 890 985 726 493 294 827 348 250 400 758 698 84 243 142 811 680 805 952 297 335 784 760 17 447 18 488 286 767 525 212 971 104 775 694 843 95 506 23 117 12 771 374 420 432 140 616 738 56 823 824 559 276 7 115 82 610 599 320 251 794 943 347 232 615 342 705 978 875 167 576 434 515 643 458 ...
output:
258109 55439 41347 29936 91129 1529 91323 0 161331 223171 2917 16836 81743 225387 271315 28686 20794 3786 24712 24049 6905 9086 1344 4945 20776 5580 5095 732 69374 2811 34365 2043 3277 32030 1 544 127699 37369 3466 230729 287399 1 5041 38025 53061 53961 2812 33811 117566 53223 24615 6645 75499 11541...
result:
ok 1000 numbers
Test #23:
score: 0
Accepted
time: 4ms
memory: 11900kb
input:
1000 1000 236 440 985 779 964 945 839 771 524 695 477 845 346 812 552 856 39 200 948 374 232 504 673 259 635 880 678 610 623 768 202 910 352 711 865 54 125 594 276 243 405 940 120 656 14 268 821 707 776 723 664 380 441 912 971 873 788 181 770 287 568 835 166 483 112 944 973 591 283 460 725 480 647 7...
output:
55099 20190 170519 95335 14104 3522 190007 38812 109137 99788 19130 785 241870 40435 2248 216604 21665 72449 157958 12958 74023 4517 28642 7299 5707 756 19499 121185 15779 69094 84017 398 224 38611 35520 53167 6 20679 6335 16415 115144 47122 55140 30903 107943 124467 21753 829 4842 130348 87613 2720...
result:
ok 1000 numbers
Test #24:
score: 0
Accepted
time: 3895ms
memory: 16180kb
input:
100000 100000 99697 62499 65369 38767 49004 41714 25240 40929 74271 97963 88205 44238 73947 88038 34453 94958 48075 26199 66549 43887 35818 48583 77453 8018 7436 18980 53885 59267 27907 86681 21554 51609 87147 5287 55193 67166 40294 1148 10152 60727 50341 38377 11343 17679 59993 52512 5533 6531 8363...
output:
1288074471 1865519129 582493609 1276924537 3161681147 129374494 54414043 1267409015 234290573 187149742 261317634 317082635 539993333 829166 156613675 2059481141 108499906 1312589341 96309609 468984063 12524390 892745811 1283743683 461204445 86654104 79621536 890662789 299705283 1097531521 174275952...
result:
ok 100000 numbers
Test #25:
score: -100
Time Limit Exceeded
input:
100000 200000 47901 40509 82712 65176 65242 38059 52717 8412 8309 57296 31699 55303 93246 95583 64025 63028 40895 19747 77421 42608 75427 38707 99837 71066 12552 13047 29149 44233 89395 78799 72754 24013 48868 40 71281 75385 42374 14591 25627 69889 73415 33560 28871 37847 1663 83908 415 60511 94235 ...