QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#507105 | #8727. Dvoboj | Physics212303 | 17 | 1098ms | 23560kb | C++17 | 720b | 2024-08-06 10:56:17 | 2024-08-06 10:56:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int n,q,l,k; cin>>n>>q,l=(k=__lg(n))>>1;
vector s(n,vector<int>(k+1));
for(int i=0;i<n;i++)
cin>>s[i][0];
auto bf=[&](int x){
for(int i=1;i<=l;i++)
for(int j=x<0?0:x;j+(1<<i)<=n&&(x<0||j+(1<<i)<=x+(1<<l));j++)
s[j][i]=abs(s[j][i-1]-s[j+(1<<i-1)][i-1]);
};
bf(-1);
while(q--){
int op,x,y; cin>>op>>x>>y;
if(x--;op==1)s[x][0]=y,bf(x);
else if(y<=l)cout<<s[x][y]<<'\n';
else{
for(int i=l+1;i<=y;i++)
for(int j=x;j+(1<<i)<=x+(1<<y);j+=1<<i)
s[j][i]=abs(s[j][i-1]-s[j+(1<<i-1)][i-1]);
cout<<s[x][y]<<'\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3812kb
input:
10 10 1361914 207572678 628126347 376128984 883488318 186963880 762865354 326392578 98149107 158171745 2 2 3 1 2 570852623 2 1 3 1 10 841056888 2 1 3 1 10 496132858 2 1 1 2 3 3 1 3 99470035 1 7 296222622
output:
260852338 214265063 214265063 206210764 68076937
result:
wrong answer 2nd numbers differ - expected: '57441684', found: '214265063'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 13
Accepted
time: 56ms
memory: 3540kb
input:
2 200000 583392119 251603292 2 1 1 2 1 1 1 1 38574148 2 1 1 2 1 1 1 1 42719181 2 1 1 1 2 536876485 1 2 761201073 1 1 335510282 2 1 1 2 1 1 2 1 1 1 2 371383902 2 1 1 2 1 1 1 1 378794551 1 1 224150551 1 2 812716786 2 1 1 2 1 1 2 1 1 1 2 129793340 2 1 1 1 1 654577279 1 1 150709706 2 1 1 1 1 883829174 1...
output:
331788827 331788827 213029144 213029144 208884111 425690791 425690791 425690791 35873620 35873620 588566235 588566235 588566235 94357211 20916366 647936652 647936652 459423963 459423963 459423963 176008535 176008535 398886231 398886231 398886231 10658183 10658183 10658183 1477309 1477309 423872241 5...
result:
ok 99810 numbers
Test #12:
score: 0
Wrong Answer
time: 60ms
memory: 3540kb
input:
8 200000 583937365 30955631 71369406 563916968 642881599 641904678 121445755 920580908 2 1 3 1 5 540256764 1 8 562659914 2 1 3 1 6 770926584 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 1 2 843982298 1 5 935286660 1 3 978153407 1 7 383158846 1 5 832692766 1 2 58984923 2 1 3 1 5 599293737 1 7 891437740 2 1 3 ...
output:
737724060 637053067 637053067 637053067 637053067 637053067 637053067 637053067 21010409 18399684 298173167 354180840 354180840 354180840 354180840 354180840 158968981 158968981 158968981 158968981 963743 11751605 11751605 319385798 319385798 147025635 147025635 147025635 147025635 147025635 1470256...
result:
wrong answer 2nd numbers differ - expected: '279132073', found: '637053067'
Subtask #3:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 23ms
memory: 3592kb
input:
10 200000 1 1 1 1 1 0 1 1 0 0 2 3 3 1 8 0 1 9 0 2 2 2 1 2 1 2 6 1 2 3 3 1 6 1 2 2 1 2 7 2 2 3 1 1 5 0 1 10 0 1 9 1 1 7 0 2 1 3 1 6 0 1 4 0 2 9 1 1 2 0 2 1 3 1 8 0 2 4 2 1 2 0 1 9 1 2 5 2 2 1 3 1 10 0 1 5 0 1 2 1 2 5 2 2 1 3 1 7 0 1 3 1 2 2 3 1 6 0 1 1 1 1 9 1 1 1 1 1 9 0 1 4 1 2 5 2 2 1 1 1 8 1 2 2 ...
output:
1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 ...
result:
wrong answer 4th numbers differ - expected: '0', found: '1'
Subtask #4:
score: 17
Accepted
Test #36:
score: 17
Accepted
time: 55ms
memory: 3524kb
input:
10 199991 37507664 194554609 209371390 279132948 336712965 55899332 339663138 116632087 630544272 741907097 2 9 1 2 1 2 2 8 1 2 5 2 2 7 2 2 3 2 2 1 1 2 2 2 2 3 2 2 8 1 2 5 2 2 1 2 2 7 2 2 3 3 2 3 3 2 2 3 2 3 3 2 8 1 2 5 2 2 5 1 2 1 3 2 1 3 2 6 2 2 2 3 2 6 2 2 3 2 2 9 1 2 1 3 2 4 1 2 5 2 2 1 3 2 7 1 ...
output:
111362825 87285387 513912185 57782582 111668226 211052075 157046945 42763236 211052075 513912185 57782582 87285387 111668226 99383849 99383849 187385143 99383849 513912185 57782582 280813633 29502805 29502805 230148379 187385143 230148379 211052075 111362825 29502805 57580017 57782582 29502805 22303...
result:
ok 199991 numbers
Test #37:
score: 17
Accepted
time: 88ms
memory: 3760kb
input:
1999 200000 205692769 142360920 151664892 907598214 795405922 175632467 244285343 27143079 276583249 298501268 10594969 264860871 214952974 216471286 246014885 813525591 366151081 791406855 51362983 564502909 189581922 488801024 260871099 259427596 33809830 12440012 89525027 18182534 403088409 93881...
output:
10520410 204683661 144721089 157181441 8767676 31099310 113863300 57257400 301671345 179722383 92608287 96776505 120405092 63649273 283985405 379036884 62468336 302138883 315150725 261999205 46435570 108353954 228065350 126017136 38656602 223207564 355228904 130380556 485499977 34426856 176542595 15...
result:
ok 200000 numbers
Test #38:
score: 17
Accepted
time: 59ms
memory: 3616kb
input:
1024 200000 171427368 578387740 923641319 332112159 660372227 184317484 276202482 214731222 677891681 628664517 833055149 570271392 241753161 234487558 32670259 674218357 54020716 531052607 520008019 191806075 297436717 788502768 352112004 27479049 102580897 740120776 653287924 182405802 907490954 7...
output:
222179270 264087568 607239683 161938730 541833994 33742387 330008592 524852243 31274322 261649596 147025256 60384021 164683325 95912771 59528864 76518957 71732881 426010432 296347460 8517321 51117678 791218739 296093606 473746837 258225768 197702322 61054072 62307227 438754389 76908556 291323598 145...
result:
ok 200000 numbers
Test #39:
score: 17
Accepted
time: 223ms
memory: 23416kb
input:
199999 199994 858673443 225964692 493295103 926194890 726822964 191538614 839676471 907887358 475466309 187972675 148234387 645774038 979838073 786366569 77592748 916010169 46589025 314047044 614039436 597031417 924219392 680302052 964935085 414872286 579200966 451774789 586257655 380628125 25411189...
output:
195151422 74045317 354109989 668325708 909574 130036022 48401780 378943645 252940094 45301279 229828868 357270630 20607800 278381743 71131999 333626235 59009713 20916013 23035881 362585098 96321131 21377714 18523649 95089918 163618210 139905062 397910821 27505980 794769294 201226982 248933 97549717 ...
result:
ok 199994 numbers
Test #40:
score: 17
Accepted
time: 196ms
memory: 23264kb
input:
200000 199991 85780249 594827653 706246193 40749596 859691670 205948107 892849857 146814285 70582796 380330815 926043741 796844866 308655323 816415533 314921371 325950271 884307536 953777742 802167806 333773046 30268328 463933386 43228669 263335047 458797584 948824637 452131582 777105540 21128358 25...
output:
46760765 2463938 18472690 68298152 221889045 36828713 220460600 7017651 138280519 16450541 129759517 90549184 85899355 62753777 139573129 361909268 147704200 258550743 232034638 35993664 27172945 22289215 16729951 267150177 271741443 7337025 153837103 6292292 57699318 250786133 557856552 82736648 26...
result:
ok 199991 numbers
Test #41:
score: 17
Accepted
time: 194ms
memory: 23364kb
input:
200000 199995 773026324 242437373 275867209 561156040 926142406 213202004 382614790 839970421 941866480 13380797 241255746 872380280 46773003 294552720 433585682 567742083 803166790 736772179 896199223 738998388 657018235 355732670 656084518 724437339 935417653 660511416 385101313 975360631 44145835...
output:
136096170 8847498 164453066 102671321 61235737 295787099 29536068 244296856 273921679 72068042 144411242 53248251 19374062 207163195 15550462 101944560 47460262 41026221 97428653 703941686 7758364 61204179 119486805 464872066 39714012 779589 116397905 39263988 128574182 13207328 5625685 20725739 975...
result:
ok 199995 numbers
Test #42:
score: 17
Accepted
time: 221ms
memory: 23464kb
input:
200000 199996 721644605 896526754 360204712 771603246 186753720 226180378 967345026 584465340 6990984 434883847 511784160 793576000 13198692 858464423 2923241 358781232 871809386 346240808 635972152 180018672 281962283 805236135 256025813 265950936 75412395 141468978 693891131 258484525 124369497 36...
output:
72215907 67574612 83886297 27627407 236864793 8614470 159865654 106027851 263804869 290587019 27876586 2171661 199382000 84763611 320356784 121735375 47474301 77425796 100409139 418257349 143704287 78735217 36294231 196430416 244212439 247203320 27462813 323585652 104918913 134879219 124120352 47170...
result:
ok 199996 numbers
Test #43:
score: 17
Accepted
time: 240ms
memory: 23344kb
input:
200000 199993 56693100 829330127 874822896 387934953 454656120 231937622 988601274 709545947 200799039 297111506 393424279 639269073 388924811 870464349 527371080 981704857 21658260 172616697 281713663 289457135 353898248 289231261 316820316 420071299 886237947 984514351 69743984 417095151 460659706...
output:
91576001 139484339 139043286 200247511 295274915 187726556 116664920 261800196 46625392 57402748 207032672 21842809 32068734 169133049 160919798 3427578 112911292 26997735 52059457 423611403 114406577 34286840 102063926 87069234 125457230 81164175 48177650 657573128 71260292 113944708 17292025 17129...
result:
ok 199993 numbers
Test #44:
score: 17
Accepted
time: 1098ms
memory: 23344kb
input:
200000 199997 731253707 677059985 692914081 289166105 782579826 314232290 754894031 880971421 255263840 212502436 317310415 856068714 643133368 504862706 21111449 731962420 740807111 920149142 65352022 43771737 841844494 988602894 646361178 737451253 92364604 918569347 520091697 529673669 957762351 ...
output:
83982747 11392887 39433748 106287787 47218495 167023628 86134094 25372157 172860611 170222919 29806395 146878014 64053013 65912929 8848898 9923668 69877059 497874 1384895 47758699 204038620 39937917 58117408 12117145 53703665 60851778 64137246 80976449 68285667 30624470 69566401 86219399 34076614 15...
result:
ok 199997 numbers
Test #45:
score: 17
Accepted
time: 1076ms
memory: 23228kb
input:
200000 199994 32036800 45890177 905865171 403688046 915481299 328641783 808100185 119865580 924122151 404893344 21410714 7106773 45659672 534911670 184731016 141902522 578525621 486170783 253447624 780513367 21635252 772234228 798331052 585914013 45637508 341910139 385965624 926151084 724713282 3077...
output:
172271959 9464712 120561794 47434834 66422598 27449620 3989759 23304032 40475455 63163370 28647039 10920778 56761208 3571534 41599880 79426907 4224428 65175389 39362441 20411200 140406907 85226776 132339679 70921417 22543498 155184903 80100433 3823845 373112881 86001472 10350124 36874973 50022664 10...
result:
ok 199994 numbers
Test #46:
score: 17
Accepted
time: 128ms
memory: 23404kb
input:
200000 199991 30610360 108645242 989911334 739961026 995122217 268969815 592181951 271322286 30071165 2716041 101327553 10776748 971703518 89966729 239574862 4181485 594546402 298237369 398608631 844595083 107410839 845912944 2750653 171379861 678550132 779381491 6274578 72227847 167942244 778615417...
output:
287017679 31478711 253099177 57591435 99666976 205090056 362714311 68995528 32782609 242870121 13941609 42071507 117358091 127306801 72634266 133269434 161173051 13505204 422561637 166242803 114291932 36373225 104543049 325395268 112733323 75787738 263645088 1909679 520636 238040150 7071530 20374833...
result:
ok 199991 numbers
Test #47:
score: 17
Accepted
time: 84ms
memory: 23560kb
input:
200000 199993 480320413 541745897 298480757 662046531 558785093 510401409 508382232 287260825 312928262 691459809 210427555 942619909 162103661 203307505 34309180 554697158 880683444 554649031 916935349 79871820 716693705 112272813 482171794 992149303 697518404 50950936 829860359 220664406 943130227...
output:
47739156 30616707 34176826 69312266 16251373 159171964 114322608 12978733 286467075 123802788 235323943 182663324 100743995 5482983 109416605 141281487 58714790 65878249 293365298 178284540 247591038 9679627 78550694 27868599 106438603 5477621 24452359 233054557 27100628 30899462 189639489 307248053...
result:
ok 199993 numbers
Test #48:
score: 17
Accepted
time: 80ms
memory: 23280kb
input:
199994 199992 868343126 24451914 40679351 695485222 520022084 945253564 957232231 874953299 792858102 462738924 925197474 475745859 379284070 675413682 820984570 985428518 159831617 19837203 43553717 936176221 455574753 757229385 176399558 43085939 26010194 25579450 763025359 349328173 32420177 4472...
output:
215595829 77739618 112442419 28622260 125667461 2384159 56762995 157209982 68779145 171863960 66047649 49770067 407962118 44992402 265105052 210354264 252569067 113743057 191040897 65549080 114108289 305699454 50831845 43150530 45451001 60416761 134717442 20383816 3022627 172091254 54610063 30160196...
result:
ok 199992 numbers
Test #49:
score: 17
Accepted
time: 141ms
memory: 23488kb
input:
199998 199998 182624015 580834220 856554234 728956680 481259075 306396664 332340406 388969484 199046117 234050808 566291103 8904578 596497247 73810802 533950904 342385287 512688845 558701664 96463030 718804333 194423034 328476901 944336378 20346290 428178273 273499 696190359 477926406 195451951 2602...
output:
80479806 53668179 79961939 84947161 6935524 221026506 20169786 141922030 87803872 164632729 35209217 65424887 97720059 3665654 47022135 114637370 17103478 10498175 29974 15409490 1732826 259864031 54502804 167706947 27657094 31090747 62228830 29262078 140236536 75878530 14500936 117880083 25145477 8...
result:
ok 199998 numbers
Test #50:
score: 17
Accepted
time: 207ms
memory: 23460kb
input:
199992 199995 570646728 63540237 598720060 762395370 442463300 741248820 781157638 976661958 678910421 5329923 207351966 615739584 813677656 545916979 246884471 773083880 865546072 23857067 223048630 501399677 7013137 973433473 638564140 71282927 830379119 974902015 629355360 606557405 358450957 678...
output:
218235492 151263290 169592567 181471212 64863492 130546315 87225985 34803044 30718999 114110588 123786036 135637998 90725518 125502122 339974640 293121637 70186415 59727970 102811042 100177284 89957465 4339533 71652444 223295805 85041589 73707105 11844093 231953439 76582146 64311003 52232254 8492664...
result:
ok 199995 numbers
Subtask #5:
score: 0
Skipped
Dependency #1:
0%