oj.uz

Submission #555464

# Submission time Handle Problem Language Result Execution time Memory
555464 2022-05-01T02:03:02 Z ngpin04 Simple game (IZhO17_game) C++14
100 / 100
 51 ms 6860 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 1e6 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

int bit[N];
int a[N];
int n,q;

void update(int pos, int val) {
	for (; pos < N; pos += pos & -pos)
		bit[pos] += val;
}

void update(int l, int r, int val) {
	if (l > r)
		swap(l, r);
	update(l, val);
	update(r + 1, -val);
}

int getval(int pos) {
	int res = 0;
	for (; pos; pos -= pos & -pos)
		res += bit[pos];
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 1; i < n; i++) 
		update(a[i], a[i + 1], 1);

	while (q--) {
		int op; cin >> op;
		if (op == 1) {
			int pos, val;
			cin >> pos >> val;
			if (pos > 1)
				update(a[pos - 1], a[pos], -1);
			if (pos < n)
				update(a[pos], a[pos + 1], -1);
			a[pos] = val;

			if (pos > 1)
				update(a[pos - 1], a[pos], 1);
			if (pos < n)
				update(a[pos], a[pos + 1], 1);
		} else {
			int v; cin >> v;
			cout << getval(v) << "\n";
		}
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 38 ms 1748 KB Output is correct
9 Correct 44 ms 6856 KB Output is correct
10 Correct 41 ms 6860 KB Output is correct
11 Correct 33 ms 1640 KB Output is correct
12 Correct 36 ms 2744 KB Output is correct
13 Correct 38 ms 2708 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 38 ms 1748 KB Output is correct
9 Correct 44 ms 6856 KB Output is correct
10 Correct 41 ms 6860 KB Output is correct
11 Correct 33 ms 1640 KB Output is correct
12 Correct 36 ms 2744 KB Output is correct
13 Correct 38 ms 2708 KB Output is correct
14 Correct 49 ms 6768 KB Output is correct
15 Correct 49 ms 6796 KB Output is correct
16 Correct 51 ms 6812 KB Output is correct
17 Correct 50 ms 6728 KB Output is correct
18 Correct 51 ms 6800 KB Output is correct