Submission #1009673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009673		nguyennh	Simple game (IZhO17_game)	C++14	100 / 100	231 ms	20716 KiB

game

#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double;
const string FILENAME = "input";
const int MAXN = 100228;
const int VAL = 1000000;
 
int n, q, a[MAXN];
int tree[4 * VAL + 228];
int lazy[4 * VAL + 228];
 
void push(int v, int tl, int tr) {
	if (tl < tr) {
		lazy[2 * v] += lazy[v];
		lazy[2 * v + 1] += lazy[v];
	}
	tree[v] += lazy[v];
	lazy[v] = 0;
}
 
void add(int v, int tl, int tr, int l, int r, int val) {
	push(v, tl, tr);
	if (l <= tl && tr <= r) {
		lazy[v] += val;
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	if (l <= tm) {
		add(2 * v, tl, tm, l, min(tm, r), val);
	}
	if (tm + 1 <= r) {
		add(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
	}
	push(2 * v, tl, tm);
	push(2 * v + 1, tm + 1, tr);
	tree[v] = tree[2 * v] + tree[2 * v + 1];
}
 
int query(int v, int tl, int tr, int x) {
	push(v, tl, tr);
	if (tl == tr) {
		return tree[v];
	}
	int tm = (tl + tr) / 2;
	if (x <= tm) {
		return query(2 * v, tl, tm, x);
	} else {
		return query(2 * v + 1, tm + 1, tr, x);
	}
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) {
		add(1, 1, VAL, min(a[i], a[i + 1]), max(a[i], a[i + 1]), 1);
	}
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int pos, val;
			cin >> pos >> val;
			if (pos != 1) {
				add(1, 1, VAL, min(a[pos - 1], a[pos]), max(a[pos - 1], a[pos]), -1);
			}
			if (pos != n) {
				add(1, 1, VAL, min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]), -1);
			}
			a[pos] = val;
			if (pos != 1) {
				add(1, 1, VAL, min(a[pos - 1], a[pos]), max(a[pos - 1], a[pos]), 1);
			}
			if (pos != n) {
				add(1, 1, VAL, min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]), 1);
			}
		} else {
			int pos;
			cin >> pos;
			cout << query(1, 1, VAL, pos) << '\n';
		}
	}
	return 0;
}

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