oj.uz

Submission #1106382

# Submission time Handle Problem Language Result Execution time Memory
1106382 2024-10-30T07:20:43 Z stdfloat Simple game (IZhO17_game) C++17
49 / 100
 41 ms 6984 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define sz(v)	(int)(v).size()
#define all(v)	(v).begin(), (v).end()

const int N = (int)1e6 + 1;

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	vector<int> a(n);
	for (auto &i : a)
		cin >> i;

	if (n <= (int)1e3) {
		while (q--) {
			int tp, x;
			cin >> tp >> x;

			if (tp == 1) {
				int vl;
				cin >> vl;

				a[--x] = vl;
			}
			else {
				int cnt = 0;
				for (int i = 0; i + 1 < n; i++)
					cnt += (min(a[i], a[i + 1]) < x && x < max(a[i], a[i + 1]));

				cout << cnt << '\n';
			}
		}
		return 0;
	}

	int rem1 = a[0], rem2 = a[n - 1];

	vector<int> cnt(N);
	for (int i = 0; i + 1 < n; i++)
		cnt[min(a[i], a[i + 1])]++;
	for (int i = N - 2; i >= 0; i--)
		cnt[i] += cnt[i + 1];

	sort(all(a));

	while (q--) {
		int tp, x;
		cin >> tp >> x;

		int y = upper_bound(all(a), x) - a.begin();
		cout << (y == n ? 0 : ((n - y - cnt[a[y]]) << 1) - (x < rem1) - (x < rem2)) << '\n';
	}
	cout << '\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 336 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 28 ms 4944 KB Output is correct
9 Correct 41 ms 6984 KB Output is correct
10 Correct 39 ms 6864 KB Output is correct
11 Correct 20 ms 5456 KB Output is correct
12 Correct 36 ms 6728 KB Output is correct
13 Correct 35 ms 6584 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 28 ms 4944 KB Output is correct
9 Correct 41 ms 6984 KB Output is correct
10 Correct 39 ms 6864 KB Output is correct
11 Correct 20 ms 5456 KB Output is correct
12 Correct 36 ms 6728 KB Output is correct
13 Correct 35 ms 6584 KB Output is correct
14 Incorrect 39 ms 6848 KB Output isn't correct
15 Halted 0 ms 0 KB -