Submission #38347

#	Time	Username	Problem	Language	Result	Execution time	Memory
38347		mirbek01	Simple game (IZhO17_game)	C++14	100 / 100	506 ms	37176 KiB

game

# include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 1e6 + 5;

typedef long long ll;

struct node{
      int sum, b;
      node(){
            sum = b = 0;
      }
}t[N * 4];

int n, m, h[N];

void push(int v, int tl, int tr){
      if(t[v].b){
            if(tl != tr){
                  t[v << 1].b += t[v].b;
                  t[(v << 1) | 1].b += t[v].b;
            }
            t[v].sum += (tr - tl + 1) * t[v].b;
            t[v].b = 0;
      }
}

void update(int l, int r, int val, int v = 1, int tl = 1, int tr = N - 2){
      push(v, tl, tr);
      if(l > tr || tl > r) return ;
      if(l <= tl && tr <= r){
            t[v].b += val;
            push(v, tl, tr);
            return ;
      }
      int tm = (tl + tr) >> 1;
      update(l, r, val, v << 1, tl, tm);
      update(l, r, val, (v << 1) | 1, tm + 1, tr);
      t[v].sum = t[v << 1].sum + t[(v << 1) | 1].sum;
}

int get(int pos, int v = 1, int tl = 1, int tr = N - 2){
      push(v, tl, tr);
      if(tl == tr) return t[v].sum;
      int tm = (tl + tr) >> 1;
      if(pos <= tm) return get(pos, v << 1, tl, tm);
      return get(pos, (v << 1) | 1, tm + 1, tr);
}

int main(){
      scanf("%d %d", &n, &m);

      for(int i = 1; i <= n; i ++)
            scanf("%d", &h[i]);

      for(int i = 2; i <= n; i ++)
            update(min(h[i - 1], h[i]), max(h[i - 1], h[i]), 1);

      while(m --){
            int type, pos, H;
            scanf("%d", &type);
            if(type == 1){
                  scanf("%d %d", &pos, &H);
                  if(pos != 1){
                        update(min(h[pos - 1], h[pos]), max(h[pos - 1], h[pos]), -1);
                        update(min(h[pos - 1], H), max(h[pos - 1], H), 1);
                  }
                  if(pos != n){
                        update(min(h[pos], h[pos + 1]), max(h[pos], h[pos + 1]), -1);
                        update(min(H, h[pos + 1]), max(H, h[pos + 1]), 1);
                  }
                  h[pos] = H;
            } else {
                  scanf("%d", &H);
                  printf("%d\n", get(H));
            }
      }
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:60:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &m);
                             ^
game.cpp:63:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &h[i]);
                               ^
game.cpp:70:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &type);
                               ^
game.cpp:72:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                   scanf("%d %d", &pos, &H);
                                           ^
game.cpp:83:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                   scanf("%d", &H);
                                  ^

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