oj.uz

Submission #648491

# Submission time Handle Problem Language Result Execution time Memory
648491 2022-10-06T17:40:36 Z ymm Simple game (IZhO17_game) C++17
100 / 100
 73 ms 6948 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1'000'010;

int fen[N];
void add(int r, int x)
{
	while (r > 0) {
		fen[r] += x;
		r -= r & -r;
	}
}
int get(int i)
{
	int ans = 0;
	++i;
	while (i < N) {
		ans += fen[i];
		i += i & -i;
	}
	return ans;
}
void add(int l, int r, int x)
{
	add(r, x);
	add(l, -x);
}

int p[N];
int n;

void add_diff(int i, int mul)
{
	int l = min(p[i], p[i+1]);
	int r = max(p[i], p[i+1]);
	add(l+1, r, mul);
}

void update_pnt(int i, int x)
{
	if (i > 0)
		add_diff(i-1, -1);
	if (i < n-1)
		add_diff(i, -1);
	p[i] = x;
	if (i > 0)
		add_diff(i-1, 1);
	if (i < n-1)
		add_diff(i, 1);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int q;
	cin >> n >> q;
	Loop (i,0,n)
		cin >> p[i];
	Loop (i,0,n-1)
		add_diff(i, 1);
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int i, y;
			cin >> i >> y;
			update_pnt(i-1, y);
		} else {
			int h;
			cin >> h;
			cout << get(h) << '\n';
		}
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4088 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 3 ms 4052 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 1 ms 340 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4088 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 35 ms 1672 KB Output is correct
9 Correct 42 ms 6792 KB Output is correct
10 Correct 41 ms 6764 KB Output is correct
11 Correct 24 ms 1484 KB Output is correct
12 Correct 36 ms 2752 KB Output is correct
13 Correct 32 ms 2764 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4088 KB Output is correct
4 Correct 2 ms 4052 KB Output is correct
5 Correct 3 ms 4052 KB Output is correct
6 Correct 3 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 35 ms 1672 KB Output is correct
9 Correct 42 ms 6792 KB Output is correct
10 Correct 41 ms 6764 KB Output is correct
11 Correct 24 ms 1484 KB Output is correct
12 Correct 36 ms 2752 KB Output is correct
13 Correct 32 ms 2764 KB Output is correct
14 Correct 70 ms 6948 KB Output is correct
15 Correct 58 ms 6732 KB Output is correct
16 Correct 66 ms 6736 KB Output is correct
17 Correct 53 ms 6816 KB Output is correct
18 Correct 73 ms 6800 KB Output is correct