oj.uz

Submission #922650

# Submission time Handle Problem Language Result Execution time Memory
922650 2024-02-05T21:40:01 Z tvladm2009 Simple game (IZhO17_game) C++17
100 / 100
 285 ms 21768 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19132 KB Output is correct
4 Correct 6 ms 19048 KB Output is correct
5 Correct 6 ms 18960 KB Output is correct
6 Correct 5 ms 19032 KB Output is correct
7 Correct 4 ms 19032 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19132 KB Output is correct
4 Correct 6 ms 19048 KB Output is correct
5 Correct 6 ms 18960 KB Output is correct
6 Correct 5 ms 19032 KB Output is correct
7 Correct 4 ms 19032 KB Output is correct
8 Correct 57 ms 12112 KB Output is correct
9 Correct 149 ms 21640 KB Output is correct
10 Correct 123 ms 21712 KB Output is correct
11 Correct 53 ms 11768 KB Output is correct
12 Correct 84 ms 12900 KB Output is correct
13 Correct 54 ms 21484 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19132 KB Output is correct
4 Correct 6 ms 19048 KB Output is correct
5 Correct 6 ms 18960 KB Output is correct
6 Correct 5 ms 19032 KB Output is correct
7 Correct 4 ms 19032 KB Output is correct
8 Correct 57 ms 12112 KB Output is correct
9 Correct 149 ms 21640 KB Output is correct
10 Correct 123 ms 21712 KB Output is correct
11 Correct 53 ms 11768 KB Output is correct
12 Correct 84 ms 12900 KB Output is correct
13 Correct 54 ms 21484 KB Output is correct
14 Correct 269 ms 21644 KB Output is correct
15 Correct 279 ms 21768 KB Output is correct
16 Correct 268 ms 21584 KB Output is correct
17 Correct 285 ms 21616 KB Output is correct
18 Correct 262 ms 21656 KB Output is correct