Pizzeriat

#include <iostream>
using namespace std;
const int N = 1<<17;
int spa[N<<1], spd[N<<1];
void set(int *sp, int i, int v) {
  i += N;
  sp[i] = v;
  while (i /= 2) {
    sp[i] = min(sp[i*2], sp[i*2+1]);
  }
}
int query(int *sp, int a, int b) {
  a += N; b += N;
  int r = 2e9;
  while (a <= b) {
    if (a&1) r = min(r, sp[a++]);
    if (~b&1) r = min(r, sp[b--]);
    a /= 2; b /= 2;
  }
  return r;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i < 2*N; ++i) spa[i] = 2e9, spd[i] = 2e9;
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; ++i) {
    int v;
    cin >> v;
    spa[N+i] = v+i;
    spd[N+i] = v+(n-i-1);
  }
  for (int i = N-1; i; --i) {
    spa[i] = min(spa[i*2], spa[i*2+1]);
    spd[i] = min(spd[i*2], spd[i*2+1]);
  }
  for (int i = 0; i < q; ++i) {
    int t, k;
    cin >> t >> k;
    k--;
    if (t == 1) {
      int v;
      cin >> v;
      set(spa, k, v+k);
      set(spd, k, v+(n-k-1));
    } else {
      int r;
      r = query(spd, 0, k)-(n-k-1);
      r = min(r, query(spa, k, n-1)-k);
      cout << r << '\n';
    }
  }
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 2

Verdict: ACCEPTED

Test 5

Group: 2

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: ACCEPTED

Test 9

Group: 3

Verdict: ACCEPTED