Submission #343251

#	Time	Username	Problem	Language	Result	Execution time	Memory
343251		ivan_tudor	Simple game (IZhO17_game)	C++14	100 / 100	72 ms	6892 KiB

game

#include<bits/stdc++.h>
using namespace std;
const int VMAX = 1e6+ 5;
const int N = 1e5 + 5;
int aib[VMAX];
void upd_aib(int poz,int val){
  for(int i = poz; i < VMAX; i+= i&(-i))
    aib[i] += val;
}
int query(int poz){
  int ans = 0;
  for(int i = poz; i>0; i-= i&(-i)){
    ans += aib[i];
  }
  return ans;
}
void update(int a, int b, int val){
  if( a > b)
    swap(a, b);
  upd_aib(a, val);
  upd_aib(b + 1, - val);
}
int v[N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, q;
  cin>>n>>q;
  for(int i=1;i<=n;i++){
    cin>>v[i];
  }
  for(int i = 2; i<=n;i++){
    update(v[i-1], v[i], 1);
  }
  for(int i=1; i<=q;i++){
    int tip;
    cin>>tip;
    if(tip == 1){
      int p, val;
      cin>>p>>val;
      if(p > 1)
        update(v[p-1], v[p], -1);
      if(p < n)
        update(v[p], v[p + 1], -1);
      v[p] = val;
      if(p > 1)
        update(v[p-1], v[p], 1);
      if(p < n)
        update(v[p], v[p + 1], 1);
    }
    else{
      int h;
      cin>>h;
      cout<<query(h)<<"\n";

    }
  }
  return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51