Pizzeriat

#include <bits/stdc++.h>

#define N (1<<17)
#define ll long long
#define ld long double
#define M 1000000007
#define INF 0x5ADFACE5
#define LINF 0x51DEEFFEC7C0DECALL
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second

using namespace std;

int l[2 * N];
int r[2 * N];
int p[N];
int n, q;

void setv(int k, int n) {
	l[k + N] = k - n;
	r[k + N] = k + n;
	k += N;
	for (k /= 2; k >= 1; k /= 2) {
		l[k] = max(l[2 * k], l[2 * k + 1]);
		r[k] = min(r[2 * k], r[2 * k + 1]);
	}
}

int lq (int i) {
	int a = 1 + N;
	int b = i + N;
	int ans = -INF;
	while (a <= b) {
		if (a & 1) ans = max(ans, l[a++]);
		if (~b & 1) ans = max(ans, l[b--]);
		a /= 2;
		b /= 2;
	}
	return ans;
}

int rq (int i) {
	int a = i + N;
	int b = n + N;
	int ans = INF;
	while (a <= b) {
		if (a & 1) ans = min(ans, r[a++]);
		if (~b & 1) ans = min(ans, r[b--]);
		a /= 2;
		b /= 2;
	}
	return ans;
}

int main () {
	cin>>n>>q;
	for (int i = 1; i <= n; i++) cin>>p[i];
	for (int i = 1; i <= n; i++) {
		setv(i, p[i]);
	}
	while (q --> 0) {
		int t;
		cin>>t;
		if (t == 1) {
			int a, b;
			cin>>a>>b;
			setv(a, b);
			p[a] = b;
		} else {
			int i;
			cin>>i;
			int ans = min(p[i], min(i - lq(i - 1), rq(i + 1) - i));
			cout<<ans<<endl;
		}
	}
}

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