CSES - IZhO 2017, day 2

Submission details
Task:	Simple game
Sender:	jarvenp
Submission time:	2019-02-10 15:08:19 +0200
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	22
#2	ACCEPTED	27
#3	ACCEPTED	51

Test results
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` view save

correct output
`2 1` view save

user output
`2 1` view save

Test 2

Group: 1, 3

Verdict: ACCEPTED

input
`1000 1000 403944 539844 451514 488113 69...` view save

correct output
`444 462 34 516 288 ...` view save

user output
`444 462 34 516 288 ...` Truncated

Test 3

Group: 1, 3

Verdict: ACCEPTED

input
`1000 1000 487368 55984 456259 117591 818...` view save

correct output
`440 400 480 130 38 ...` view save

user output
`440 400 480 130 38 ...` Truncated

Test 4

Group: 1, 3

Verdict: ACCEPTED

input
`1000 1000 570792 604828 236813 971260 13...` view save

correct output
`386 460 50 470 126 ...` view save

user output
`386 460 50 470 126 ...` Truncated

Test 5

Group: 1, 3

Verdict: ACCEPTED

input
`1000 1000 686920 120969 241559 600738 48...` view save

correct output
`330 306 418 290 136 ...` view save

user output
`330 306 418 290 136 ...` Truncated

Test 6

Group: 1, 3

Verdict: ACCEPTED

input
`1000 1000 737640 478325 54816 262919 609...` view save

correct output
`230 418 148 338 4 ...` view save

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 ...` view save

correct output
`999 999 999 999 999 ...` view save

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...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` Truncated

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`100000 100000 611680 625326 848926 304761 34...` view save

correct output
`30636 30745 50130 4464 9086 ...` view save

user output
`30636 30745 50130 4464 9086 ...` Truncated

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
`100000 100000 695104 174171 853672 901534 35...` view save

correct output
`31870 39772 30788 11144 42732 ...` view save

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 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` Truncated

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
`100000 100000 2845 22894 4105 11830 29440 21...` view save

correct output
`45066 50090 24109 27778 294 ...` view save

user output
`45066 50090 24109 27778 294 ...` Truncated

Test 13

Group: 3

Verdict: ACCEPTED

input
`100000 100000 123269 247698 241557 639404 38...` view save

correct output
`37412 1520 46224 964 50058 ...` view save

user output
`37412 1520 46224 964 50058 ...` Truncated

Test 14

Group: 3

Verdict: ACCEPTED

input
`100000 100000 206693 572351 22110 493074 737...` view save

correct output
`33086 49042 43971 17756 41889 ...` view save

user output
`33086 49042 43971 17756 41889 ...` Truncated

Test 15

Group: 3

Verdict: ACCEPTED

input
`100000 100000 322821 121195 59560 155256 829...` view save

correct output
`28252 45031 28212 6208 31642 ...` view save

user output
`28252 45031 28212 6208 31642 ...` Truncated

Test 16

Group: 3

Verdict: ACCEPTED

input
`100000 100000 438949 637336 872818 784733 17...` view save

correct output
`45374 22320 9690 5630 40012 ...` view save

user output
`45374 22320 9690 5630 40012 ...` Truncated

Test 17

Group: 3

Verdict: ACCEPTED

input
`100000 100000 489669 186180 653371 446915 52...` view save

correct output
`43104 43128 41430 35554 996 ...` view save

user output
`43104 43128 41430 35554 996 ...` Truncated

Test 18

Group: 2, 3

Verdict: ACCEPTED

input
`100000 100000 1 1000000 1 1000000 1 1000000 ...` view save

correct output
`99999 99999 99999 99999 99999 ...` view save

user output
`99999 99999 99999 99999 99999 ...` Truncated

IZhO 2017, day 2

Simple game

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Tasks

Submissions (jarvenp)