oj.uz

Submission #879652

# Submission time Handle Problem Language Result Execution time Memory
879652 2023-11-27T19:35:14 Z alex_2008 Simple game (IZhO17_game) C++14
100 / 100
 196 ms 20724 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <unordered_map>
#include <fstream>
#include <random>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
int fenwick1[N], fenwick2[N], a[N], mn[N], mx[N];
int MAX_V = 1000000;
void update1(int pos, int val) {
	while (pos <= MAX_V) {
		fenwick1[pos] += val;
		pos += (pos & (-pos));
	}
}
int sum1(int pos) {
	int ans = 0;
	while (pos > 0) {
		ans += fenwick1[pos];
		pos -= (pos & (-pos));
	}
	return ans;
}
void update2(int pos, int val) {
	while (pos <= MAX_V) {
		fenwick2[pos] += val;
		pos += (pos & (-pos));
	}
}
int sum2(int pos) {
	int ans = 0;
	while (pos > 0) {
		ans += fenwick2[pos];
		pos -= (pos & (-pos));
	}
	return ans;
}
int main() {
	int n, m;
	cin >> n >> m;
	map <int, int> mp;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n - 1; i++) {
		mn[i] = min(a[i], a[i + 1]);
		mx[i] = max(a[i], a[i + 1]);
		update1(mn[i], 1);
		update2(mx[i], 1);
	}
	while (m--) {
		int type;
		cin >> type;
		if (type == 2) {
			int H;
			cin >> H;
			int v1 = sum1(MAX_V) - sum1(H);
			int v2 = sum2(H - 1);
			cout << n - 1 - v1 - v2 << "\n";
		}
		else {
			int x, val;
			cin >> x >> val;
			for (int ind = x - 1; ind <= x; ind++) {
				if (ind > 0 && ind < n) {
					update1(mn[ind], -1);
					update2(mx[ind], -1);
				}
			}
			a[x] = val;
			for (int ind = x - 1; ind <= x; ind++) {
				if (ind > 0 && ind < n) {
					mn[ind] = min(a[ind], a[ind + 1]);
					mx[ind] = max(a[ind], a[ind + 1]);
				}
			}
			for (int ind = x - 1; ind <= x; ind++) {
				if (ind > 0 && ind < n) {
					update1(mn[ind], 1);
					update2(mx[ind], 1);
				}
			}
		}
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 3 ms 13148 KB Output is correct
4 Correct 3 ms 13204 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 3 ms 8536 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 3 ms 13148 KB Output is correct
4 Correct 3 ms 13204 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 3 ms 8536 KB Output is correct
8 Correct 167 ms 18048 KB Output is correct
9 Correct 185 ms 20148 KB Output is correct
10 Correct 187 ms 20088 KB Output is correct
11 Correct 162 ms 18144 KB Output is correct
12 Correct 175 ms 18772 KB Output is correct
13 Correct 196 ms 14932 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 3 ms 13148 KB Output is correct
4 Correct 3 ms 13204 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 3 ms 8536 KB Output is correct
8 Correct 167 ms 18048 KB Output is correct
9 Correct 185 ms 20148 KB Output is correct
10 Correct 187 ms 20088 KB Output is correct
11 Correct 162 ms 18144 KB Output is correct
12 Correct 175 ms 18772 KB Output is correct
13 Correct 196 ms 14932 KB Output is correct
14 Correct 144 ms 20292 KB Output is correct
15 Correct 144 ms 20048 KB Output is correct
16 Correct 144 ms 20048 KB Output is correct
17 Correct 152 ms 20724 KB Output is correct
18 Correct 149 ms 20048 KB Output is correct