Task: | Kaaleppi's run |
Sender: | Tuukka Korhonen |
Submission time: | 2016-10-03 15:33:51 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.12 s | details |
#2 | ACCEPTED | 0.17 s | details |
#3 | ACCEPTED | 0.17 s | details |
#4 | ACCEPTED | 0.10 s | details |
#5 | ACCEPTED | 0.16 s | details |
#6 | ACCEPTED | 0.10 s | details |
#7 | ACCEPTED | 0.12 s | details |
#8 | ACCEPTED | 0.07 s | details |
#9 | ACCEPTED | 0.18 s | details |
#10 | ACCEPTED | 0.13 s | details |
#11 | ACCEPTED | 0.20 s | details |
#12 | ACCEPTED | 0.19 s | details |
#13 | ACCEPTED | 0.20 s | details |
#14 | ACCEPTED | 0.21 s | details |
#15 | ACCEPTED | 0.21 s | details |
#16 | ACCEPTED | 0.20 s | details |
#17 | ACCEPTED | 0.20 s | details |
#18 | ACCEPTED | 0.19 s | details |
#19 | ACCEPTED | 0.20 s | details |
#20 | ACCEPTED | 0.20 s | details |
#21 | ACCEPTED | 0.20 s | details |
#22 | ACCEPTED | 0.21 s | details |
#23 | ACCEPTED | 0.20 s | details |
#24 | ACCEPTED | 0.21 s | details |
#25 | ACCEPTED | 0.19 s | details |
#26 | ACCEPTED | 0.20 s | details |
#27 | ACCEPTED | 0.21 s | details |
#28 | ACCEPTED | 0.19 s | details |
#29 | ACCEPTED | 0.20 s | details |
#30 | ACCEPTED | 0.20 s | details |
Code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1<<18; ll sst[2*N]; ll mst[2*N]; void run(int i, int stl, int str, int l, int r, ll k){ if (stl>r||str<l) return; if (mst[i]<k) return; if (stl==str){ sst[i]%=k; mst[i]%=k; } else{ int m=(stl+str)/2; run(i*2, stl, m, l, r, k); run(i*2+1, m+1, str, l, r, k); mst[i]=max(mst[i*2], mst[i*2+1]); sst[i]=sst[i*2]+sst[i*2+1]; } } ll sum(int a, int b){ a+=N; b+=N; ll su=0; while (a<=b){ if (a%2) su+=sst[a++]; if (!(b%2)) su+=sst[b--]; a/=2; b/=2; } return su; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,q; cin>>n>>q; assert(1<=n&&n<=200000); assert(1<=q&&q<=200000); for (int i=1;i<=n;i++){ int a; cin>>a; assert(1<=a&&a<=1e9); mst[N+i]=a; sst[N+i]=a; } for (int i=N-1;i>=1;i--){ mst[i]=max(mst[i*2], mst[i*2+1]); sst[i]=sst[i*2]+sst[i*2+1]; } for (int qq=0;qq<q;qq++){ int t,l,r; cin>>t>>l>>r; assert(t==1||t==2); assert(1<=l&&l<=r&&r<=n); if (t==2){ cout<<sum(l, r)<<'\n'; } else{ int k; cin>>k; assert(1<=k&&k<=1e9); run(1, 0, N-1, l, r, k); } } }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
89384 130887 681692778 714636916 957747794 ... |
correct output |
---|
3568050627345 4840079633895 4979742617229 3278015536236 8227531490884 ... |
user output |
---|
3568050627345 4840079633895 4979742617229 3278015536236 8227531490884 ... |
Test 2
Verdict: ACCEPTED
input |
---|
110132 199724 847570814 404978775 106367318 ... |
correct output |
---|
1427981161528 6256316123063 1076159707539 1525408287745 12452883393272 ... |
user output |
---|
1427981161528 6256316123063 1076159707539 1525408287745 12452883393272 ... |
Test 3
Verdict: ACCEPTED
input |
---|
87738 181088 562855988 84781032 926253527 7... |
correct output |
---|
5716947015138 14424560752621 3616168262601 807226877121 83465638349 ... |
user output |
---|
5716947015138 14424560752621 3616168262601 807226877121 83465638349 ... |
Test 4
Verdict: ACCEPTED
input |
---|
158114 63223 462120872 498977056 463223297 ... |
correct output |
---|
49126485898374 2184603743669 23961846093944 2848201705457 1555275733993 ... |
user output |
---|
49126485898374 2184603743669 23961846093944 2848201705457 1555275733993 ... |
Test 5
Verdict: ACCEPTED
input |
---|
140966 138126 812693646 252682523 265941575 ... |
correct output |
---|
22817793228905 17812780427335 2620152643855 2866263272648 5009940526564 ... |
user output |
---|
22817793228905 17812780427335 2620152643855 2866263272648 5009940526564 ... |
Test 6
Verdict: ACCEPTED
input |
---|
70958 64685 892097055 124053711 989231834 ... |
correct output |
---|
460637799671 1475480287645 3957671266357 15189222079188 8068328407783 ... |
user output |
---|
460637799671 1475480287645 3957671266357 15189222079188 8068328407783 ... |
Test 7
Verdict: ACCEPTED
input |
---|
97044 123753 707926206 599809760 994891636 ... |
correct output |
---|
30504891581 10585850358828 3752130598295 4274674534895 18961318419991 ... |
user output |
---|
30504891581 10585850358828 3752130598295 4274674534895 18961318419991 ... |
Test 8
Verdict: ACCEPTED
input |
---|
25458 9623 313230374 496638350 562858459 ... |
correct output |
---|
348560018107 5323872135694 28101423541 5060603534783 8455422896644 ... |
user output |
---|
348560018107 5323872135694 28101423541 5060603534783 8455422896644 ... |
Test 9
Verdict: ACCEPTED
input |
---|
161390 197159 674040671 808300128 26080705 9... |
correct output |
---|
6338494962280 9308586268339 1426570147836 619729941732 531996459059 ... |
user output |
---|
6338494962280 9308586268339 1426570147836 619729941732 531996459059 ... |
Test 10
Verdict: ACCEPTED
input |
---|
183342 96224 100979382 831921884 895353059 ... |
correct output |
---|
4146493190203 29755052359871 21010351347658 4994403502744 4874048764601 ... |
user output |
---|
4146493190203 29755052359871 21010351347658 4994403502744 4874048764601 ... |
Test 11
Verdict: ACCEPTED
input |
---|
200000 200000 163516132 88718522 960501684 3... |
correct output |
---|
8705161776177 16560680715170 4529140494185 22215511151267 307663601912 ... |
user output |
---|
8705161776177 16560680715170 4529140494185 22215511151267 307663601912 ... |
Test 12
Verdict: ACCEPTED
input |
---|
200000 200000 661328518 295428034 543539165 ... |
correct output |
---|
44125316835086 12534063038672 13779878669135 1110457357385 53890550863397 ... |
user output |
---|
44125316835086 12534063038672 13779878669135 1110457357385 53890550863397 ... |
Test 13
Verdict: ACCEPTED
input |
---|
200000 200000 835492064 858947595 489705704 ... |
correct output |
---|
7123736494948 18343643800481 4061553943570 22394824679259 17059560008797 ... |
user output |
---|
7123736494948 18343643800481 4061553943570 22394824679259 17059560008797 ... |
Test 14
Verdict: ACCEPTED
input |
---|
200000 200000 357734101 493956933 250155363 ... |
correct output |
---|
19974989429712 60252072248233 45678027522989 9906096645143 5796576869969 ... |
user output |
---|
19974989429712 60252072248233 45678027522989 9906096645143 5796576869969 ... |
Test 15
Verdict: ACCEPTED
input |
---|
200000 200000 366056556 485208318 898983115 ... |
correct output |
---|
18324415144074 1960721236822 262868810399 418650395034 4926733633202 ... |
user output |
---|
18324415144074 1960721236822 262868810399 418650395034 4926733633202 ... |
Test 16
Verdict: ACCEPTED
input |
---|
200000 200000 696545081 391575800 525194671 ... |
correct output |
---|
464526195732 10421706643804 25715510077679 60768424352308 47109574794106 ... |
user output |
---|
464526195732 10421706643804 25715510077679 60768424352308 47109574794106 ... |
Test 17
Verdict: ACCEPTED
input |
---|
200000 200000 785409780 12543965 724522794 5... |
correct output |
---|
76078073776916 12550437486909 1961851552333 3704172183345 958583269110 ... |
user output |
---|
76078073776916 12550437486909 1961851552333 3704172183345 958583269110 ... |
Test 18
Verdict: ACCEPTED
input |
---|
200000 200000 239188181 76186945 538812873 7... |
correct output |
---|
9965856033901 22841982053808 20057247487740 22036414753777 743665836923 ... |
user output |
---|
9965856033901 22841982053808 20057247487740 22036414753777 743665836923 ... |
Test 19
Verdict: ACCEPTED
input |
---|
200000 200000 571088696 713137765 869808231 ... |
correct output |
---|
27201871131366 1773925165749 21331314450495 44597922896 11839927329463 ... |
user output |
---|
27201871131366 1773925165749 21331314450495 44597922896 11839927329463 ... |
Test 20
Verdict: ACCEPTED
input |
---|
200000 200000 94357126 167500952 625424533 7... |
correct output |
---|
19827596131079 1587873460955 56673140705204 1825224125411 14126369552503 ... |
user output |
---|
19827596131079 1587873460955 56673140705204 1825224125411 14126369552503 ... |
Test 21
Verdict: ACCEPTED
input |
---|
200000 200000 902289752 980717302 482700427 ... |
correct output |
---|
42722728269555 32652085471516 7532635788308 26365360928406 31706902704494 ... |
user output |
---|
42722728269555 32652085471516 7532635788308 26365360928406 31706902704494 ... |
Test 22
Verdict: ACCEPTED
input |
---|
200000 200000 234861789 896308950 585257292 ... |
correct output |
---|
23148184769579 6264813675999 47314176314048 17697735609162 2251160486380 ... |
user output |
---|
23148184769579 6264813675999 47314176314048 17697735609162 2251160486380 ... |
Test 23
Verdict: ACCEPTED
input |
---|
200000 200000 889896556 543224603 961078149 ... |
correct output |
---|
1713650642846 35249443235523 9622564970592 20993151478096 559043197323 ... |
user output |
---|
1713650642846 35249443235523 9622564970592 20993151478096 559043197323 ... |
Test 24
Verdict: ACCEPTED
input |
---|
200000 200000 995332283 686573056 932431685 ... |
correct output |
---|
12013196028573 47655633640876 18257672284868 27625651650511 46438192959164 ... |
user output |
---|
12013196028573 47655633640876 18257672284868 27625651650511 46438192959164 ... |
Test 25
Verdict: ACCEPTED
input |
---|
200000 200000 946315600 868557890 318443283 ... |
correct output |
---|
1133762533395 57398145786924 869840469415 29146044858314 35199351262230 ... |
user output |
---|
1133762533395 57398145786924 869840469415 29146044858314 35199351262230 ... |
Test 26
Verdict: ACCEPTED
input |
---|
200000 200000 944060128 254626749 68890590 2... |
correct output |
---|
11055994363482 2657055498612 30597070068344 7792687527844 7661261162964 ... |
user output |
---|
11055994363482 2657055498612 30597070068344 7792687527844 7661261162964 ... |
Test 27
Verdict: ACCEPTED
input |
---|
200000 200000 841299688 308557219 620166698 ... |
correct output |
---|
19393456997210 195469629029 2786427435737 1993020037538 3164725175677 ... |
user output |
---|
19393456997210 195469629029 2786427435737 1993020037538 3164725175677 ... |
Test 28
Verdict: ACCEPTED
input |
---|
200000 200000 494252927 946174799 609845025 ... |
correct output |
---|
15907022632481 27292668068962 441027352490 40834476272262 28481559993407 ... |
user output |
---|
15907022632481 27292668068962 441027352490 40834476272262 28481559993407 ... |
Test 29
Verdict: ACCEPTED
input |
---|
200000 200000 470856857 625269921 288612820 ... |
correct output |
---|
2046228565150 3617420568401 1053973762226 5913120807902 5419236217968 ... |
user output |
---|
2046228565150 3617420568401 1053973762226 5913120807902 5419236217968 ... |
Test 30
Verdict: ACCEPTED
input |
---|
200000 200000 62623182 70087409 956344115 19... |
correct output |
---|
28081481609073 287568565804 2709243279569 5210936812890 12514447288598 ... |
user output |
---|
28081481609073 287568565804 2709243279569 5210936812890 12514447288598 ... |