oj.uz

Submission #344841

# Submission time Handle Problem Language Result Execution time Memory
344841 2021-01-06T15:58:44 Z SeDunion Simple game (IZhO17_game) C++17
100 / 100
 125 ms 10860 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

int Mx[N], Mn[N];
void MxUpd(int pos, int val) {
	while (pos < N) {
		Mx[pos] += val;
		pos |= pos + 1;
	}
}
int MxGet(int pos) {
	int res = 0;
	while (pos >= 0) {
		res += Mx[pos];
		pos &= pos + 1, pos--;
	}
	return res;
}
void MnUpd(int pos, int val) {
	while (pos < N) {
		Mn[pos] += val;
		pos |= pos + 1;
	}
}
int MnGet(int pos) {
	int res = 0;
	while (pos >= 0) {
		res += Mn[pos];
		pos &= pos + 1, pos--;
	}
	return res;
}

int n, m, a[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1 ; i <= n ; ++ i) {
		cin >> a[i];
	}
	for (int i = 2 ; i <= n ; ++ i) {
		MxUpd(max(a[i], a[i - 1]), 1);
		MnUpd(min(a[i], a[i - 1]), 1);
	}
	for (int t, x, y ; m-- ; ) {
		cin >> t >> x;
		if (t == 1) {
			cin >> y;
			if (x > 1) MxUpd(max(a[x], a[x - 1]), -1), MnUpd(min(a[x], a[x - 1]), -1);
			if (x < n) MxUpd(max(a[x], a[x + 1]), -1), MnUpd(min(a[x], a[x + 1]), -1);
			a[x] = y;
			if (x > 1) MxUpd(max(a[x], a[x - 1]), +1), MnUpd(min(a[x], a[x - 1]), +1);
			if (x < n) MxUpd(max(a[x], a[x + 1]), +1), MnUpd(min(a[x], a[x + 1]), +1);
		} else {
			//cout << MxGet(N - 1) - MxGet(x) << " " << MnGet(x) << "\n";
			cout << (n - 1) - (MnGet(N - 1) - MnGet(x)) - (MxGet(x)) << "\n";
		}
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 6 ms 7020 KB Output is correct
3 Correct 5 ms 7020 KB Output is correct
4 Correct 5 ms 7040 KB Output is correct
5 Correct 5 ms 6892 KB Output is correct
6 Correct 5 ms 7020 KB Output is correct
7 Correct 2 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 6 ms 7020 KB Output is correct
3 Correct 5 ms 7020 KB Output is correct
4 Correct 5 ms 7040 KB Output is correct
5 Correct 5 ms 6892 KB Output is correct
6 Correct 5 ms 7020 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 51 ms 1980 KB Output is correct
9 Correct 125 ms 10860 KB Output is correct
10 Correct 66 ms 10860 KB Output is correct
11 Correct 44 ms 1772 KB Output is correct
12 Correct 47 ms 3052 KB Output is correct
13 Correct 48 ms 2924 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 6 ms 7020 KB Output is correct
3 Correct 5 ms 7020 KB Output is correct
4 Correct 5 ms 7040 KB Output is correct
5 Correct 5 ms 6892 KB Output is correct
6 Correct 5 ms 7020 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 51 ms 1980 KB Output is correct
9 Correct 125 ms 10860 KB Output is correct
10 Correct 66 ms 10860 KB Output is correct
11 Correct 44 ms 1772 KB Output is correct
12 Correct 47 ms 3052 KB Output is correct
13 Correct 48 ms 2924 KB Output is correct
14 Correct 90 ms 10860 KB Output is correct
15 Correct 92 ms 10832 KB Output is correct
16 Correct 94 ms 10808 KB Output is correct
17 Correct 83 ms 10732 KB Output is correct
18 Correct 81 ms 10732 KB Output is correct