Task: | Simple game |
Sender: | jarvenp |
Submission time: | 2019-02-10 15:08:19 +0200 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 22 |
#2 | ACCEPTED | 27 |
#3 | ACCEPTED | 51 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.04 s | 1, 3 | details |
#2 | ACCEPTED | 0.03 s | 1, 3 | details |
#3 | ACCEPTED | 0.03 s | 1, 3 | details |
#4 | ACCEPTED | 0.03 s | 1, 3 | details |
#5 | ACCEPTED | 0.03 s | 1, 3 | details |
#6 | ACCEPTED | 0.03 s | 1, 3 | details |
#7 | ACCEPTED | 0.04 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.08 s | 2, 3 | details |
#9 | ACCEPTED | 0.10 s | 2, 3 | details |
#10 | ACCEPTED | 0.10 s | 2, 3 | details |
#11 | ACCEPTED | 0.07 s | 2, 3 | details |
#12 | ACCEPTED | 0.09 s | 2, 3 | details |
#13 | ACCEPTED | 0.12 s | 3 | details |
#14 | ACCEPTED | 0.12 s | 3 | details |
#15 | ACCEPTED | 0.13 s | 3 | details |
#16 | ACCEPTED | 0.12 s | 3 | details |
#17 | ACCEPTED | 0.12 s | 3 | details |
#18 | ACCEPTED | 0.09 s | 2, 3 | details |
Code
#include <bits/stdc++.h>#include <stdint.h>using namespace std;int64_t puu[1<<21];int64_t n,m;const int64_t size = 1<<21;int64_t t[100000];void muuta(int64_t index, int64_t val){index += size/2;puu[index] = val;for(index/=2; index >0; index/=2){puu[index] = puu[index*2]+puu[index*2+1];}}void muutos(int64_t index1, int64_t index2){if(t[index1] < t[index2]){muuta(t[index1],puu[t[index1]+size/2]+1);muuta(t[index2],puu[t[index2]+size/2]-1);}else if(t[index1] > t[index2]){muuta(t[index2],puu[t[index2]+size/2]+1);muuta(t[index1],puu[t[index1]+size/2]-1);}}int64_t summa(int64_t a,int64_t b){a+= size/2;b+= size/2;int64_t s = 0;while(a <= b){if(a%2 == 1){s += puu[a];a++;}if(b%2 == 0){s += puu[b];b--;}a/=2;b/=2;}return s;}int main(){ios_base::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for(int64_t i=0; i<n; i++){cin >> t[i];}for(int64_t i=0; i<size; i++){puu[i] = 0;}for(int64_t i=0; i<(n-1); i++){muutos(i,i+1);}for(int64_t i=0; i<m; i++){int64_t temp;cin >> temp;if(temp == 1){int64_t pos,val;cin >> pos >> val;pos--;if(pos > 0){if(t[pos] > t[pos-1]){muuta(t[pos-1],puu[t[pos-1]+size/2]-1);muuta(t[pos],puu[t[pos]+size/2]+1);}else if(t[pos] < t[pos-1]){muuta(t[pos],puu[t[pos]+size/2]-1);muuta(t[pos-1],puu[t[pos-1]+size/2]+1);}}if(pos < (n-1)){if(t[pos] < t[pos+1]){muuta(t[pos+1],puu[t[pos+1]+size/2]+1);muuta(t[pos],puu[t[pos]+size/2]-1);}else if(t[pos] > t[pos+1]){muuta(t[pos],puu[t[pos]+size/2]+1);muuta(t[pos+1],puu[t[pos+1]+size/2]-1);}}t[pos] = val;if(pos > 0){muutos(pos,pos-1);}if(pos < (n-1)){muutos(pos,pos+1);}}else{int64_t h;cin >> h;cout << summa(0,h) << "\n";}}}
Test details
Test 1
Group: 1, 3
Verdict: ACCEPTED
input |
---|
3 3 1 5 1 2 3 1 1 5 2 3 |
correct output |
---|
2 1 |
user output |
---|
2 1 |
Test 2
Group: 1, 3
Verdict: ACCEPTED
input |
---|
1000 1000 403944 539844 451514 488113 69... |
correct output |
---|
444 462 34 516 288 ... |
user output |
---|
444 462 34 516 288 ... Truncated |
Test 3
Group: 1, 3
Verdict: ACCEPTED
input |
---|
1000 1000 487368 55984 456259 117591 818... |
correct output |
---|
440 400 480 130 38 ... |
user output |
---|
440 400 480 130 38 ... Truncated |
Test 4
Group: 1, 3
Verdict: ACCEPTED
input |
---|
1000 1000 570792 604828 236813 971260 13... |
correct output |
---|
386 460 50 470 126 ... |
user output |
---|
386 460 50 470 126 ... Truncated |
Test 5
Group: 1, 3
Verdict: ACCEPTED
input |
---|
1000 1000 686920 120969 241559 600738 48... |
correct output |
---|
330 306 418 290 136 ... |
user output |
---|
330 306 418 290 136 ... Truncated |
Test 6
Group: 1, 3
Verdict: ACCEPTED
input |
---|
1000 1000 737640 478325 54816 262919 609... |
correct output |
---|
230 418 148 338 4 ... |
user output |
---|
230 418 148 338 4 ... Truncated |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1000 1000 1 1000000 1 1000000 1 1000000 ... |
correct output |
---|
999 999 999 999 999 ... |
user output |
---|
999 999 999 999 999 ... Truncated |
Test 8
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100000 100000 18 15 8 5 7 19 19 11 11 8 6 15... |
correct output |
---|
0 0 0 0 0 ... |
user output |
---|
0 0 0 0 0 ... Truncated |
Test 9
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100000 100000 611680 625326 848926 304761 34... |
correct output |
---|
30636 30745 50130 4464 9086 ... |
user output |
---|
30636 30745 50130 4464 9086 ... Truncated |
Test 10
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100000 100000 695104 174171 853672 901534 35... |
correct output |
---|
31870 39772 30788 11144 42732 ... |
user output |
---|
31870 39772 30788 11144 42732 ... Truncated |
Test 11
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100000 100000 1 1 1 2 1 1 2 1 2 2 1 2 2 1 1 ... |
correct output |
---|
0 0 0 0 0 ... |
user output |
---|
0 0 0 0 0 ... Truncated |
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100000 100000 2845 22894 4105 11830 29440 21... |
correct output |
---|
45066 50090 24109 27778 294 ... |
user output |
---|
45066 50090 24109 27778 294 ... Truncated |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
100000 100000 123269 247698 241557 639404 38... |
correct output |
---|
37412 1520 46224 964 50058 ... |
user output |
---|
37412 1520 46224 964 50058 ... Truncated |
Test 14
Group: 3
Verdict: ACCEPTED
input |
---|
100000 100000 206693 572351 22110 493074 737... |
correct output |
---|
33086 49042 43971 17756 41889 ... |
user output |
---|
33086 49042 43971 17756 41889 ... Truncated |
Test 15
Group: 3
Verdict: ACCEPTED
input |
---|
100000 100000 322821 121195 59560 155256 829... |
correct output |
---|
28252 45031 28212 6208 31642 ... |
user output |
---|
28252 45031 28212 6208 31642 ... Truncated |
Test 16
Group: 3
Verdict: ACCEPTED
input |
---|
100000 100000 438949 637336 872818 784733 17... |
correct output |
---|
45374 22320 9690 5630 40012 ... |
user output |
---|
45374 22320 9690 5630 40012 ... Truncated |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
100000 100000 489669 186180 653371 446915 52... |
correct output |
---|
43104 43128 41430 35554 996 ... |
user output |
---|
43104 43128 41430 35554 996 ... Truncated |
Test 18
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100000 100000 1 1000000 1 1000000 1 1000000 ... |
correct output |
---|
99999 99999 99999 99999 99999 ... |
user output |
---|
99999 99999 99999 99999 99999 ... Truncated |