oj.uz

Submission #957429

# Submission time Handle Problem Language Result Execution time Memory
957429 2024-04-03T17:00:09 Z starchan Simple game (IZhO17_game) C++17
100 / 100
 72 ms 11160 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
const int LMX  = 1e6+6;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int fen[LMX];
void upd(int x, int val)
{
	for(int pos = x; pos < LMX; pos+=(pos&-pos))
		fen[pos]+=val;
	return;
}
int query(int x)
{
	int ret = 0;
	for(int pos = x; pos; pos-=(pos&-pos))
		ret+=fen[pos];
	return ret;
}
void add(int l, int r, int d)
{
	if(l > r)
		swap(l, r);
	upd(l, d); upd(r+1, -d);
	return;
}
signed main()
{
	fast();
	int n, m;
	cin >> n >> m;
	vector<int> h(n+1);
	for(int i = 1; i <= n; i++)
	{
		cin >> h[i];
		if(i > 1)
			add(h[i-1], h[i], 1);
	}
	while(m--)
	{
		int t, x; cin >> t >> x; t--;
		if(t)
			cout << query(x) << "\n";
		else
		{
			if(x > 1)
				add(h[x-1], h[x], -1);
			if(x < n)
				add(h[x], h[x+1], -1);
			cin >> h[x];
			if(x > 1)
				add(h[x-1], h[x], 1);
			if(x < n)
				add(h[x], h[x+1], 1);
		}
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Correct 2 ms 7916 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Correct 2 ms 7916 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 27 ms 6260 KB Output is correct
9 Correct 33 ms 11088 KB Output is correct
10 Correct 35 ms 11092 KB Output is correct
11 Correct 29 ms 6068 KB Output is correct
12 Correct 29 ms 7516 KB Output is correct
13 Correct 29 ms 7240 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 3 ms 7772 KB Output is correct
6 Correct 2 ms 7916 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 27 ms 6260 KB Output is correct
9 Correct 33 ms 11088 KB Output is correct
10 Correct 35 ms 11092 KB Output is correct
11 Correct 29 ms 6068 KB Output is correct
12 Correct 29 ms 7516 KB Output is correct
13 Correct 29 ms 7240 KB Output is correct
14 Correct 45 ms 11092 KB Output is correct
15 Correct 72 ms 11044 KB Output is correct
16 Correct 45 ms 11088 KB Output is correct
17 Correct 43 ms 11108 KB Output is correct
18 Correct 50 ms 11160 KB Output is correct