oj.uz

Submission #38347

# Submission time Handle Problem Language Result Execution time Memory
38347 2018-01-04T03:20:58 Z mirbek01 Simple game (IZhO17_game) C++14
100 / 100
 506 ms 37176 KB 
# 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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37176 KB Output is correct
2 Correct 16 ms 37176 KB Output is correct
3 Correct 19 ms 37176 KB Output is correct
4 Correct 19 ms 37176 KB Output is correct
5 Correct 16 ms 37176 KB Output is correct
6 Correct 6 ms 37176 KB Output is correct
7 Correct 16 ms 37176 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37176 KB Output is correct
2 Correct 16 ms 37176 KB Output is correct
3 Correct 19 ms 37176 KB Output is correct
4 Correct 19 ms 37176 KB Output is correct
5 Correct 16 ms 37176 KB Output is correct
6 Correct 6 ms 37176 KB Output is correct
7 Correct 16 ms 37176 KB Output is correct
8 Correct 76 ms 37176 KB Output is correct
9 Correct 219 ms 37176 KB Output is correct
10 Correct 249 ms 37176 KB Output is correct
11 Correct 89 ms 37176 KB Output is correct
12 Correct 139 ms 37176 KB Output is correct
13 Correct 169 ms 37176 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37176 KB Output is correct
2 Correct 16 ms 37176 KB Output is correct
3 Correct 19 ms 37176 KB Output is correct
4 Correct 19 ms 37176 KB Output is correct
5 Correct 16 ms 37176 KB Output is correct
6 Correct 6 ms 37176 KB Output is correct
7 Correct 16 ms 37176 KB Output is correct
8 Correct 76 ms 37176 KB Output is correct
9 Correct 219 ms 37176 KB Output is correct
10 Correct 249 ms 37176 KB Output is correct
11 Correct 89 ms 37176 KB Output is correct
12 Correct 139 ms 37176 KB Output is correct
13 Correct 169 ms 37176 KB Output is correct
14 Correct 483 ms 37176 KB Output is correct
15 Correct 429 ms 37176 KB Output is correct
16 Correct 466 ms 37176 KB Output is correct
17 Correct 506 ms 37176 KB Output is correct
18 Correct 486 ms 37176 KB Output is correct