oj.uz

Submission #475152

# Submission time Handle Problem Language Result Execution time Memory
475152 2021-09-21T10:17:01 Z ismoilov Simple game (IZhO17_game) C++14
100 / 100
 75 ms 6868 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int maxx = 2e6;

int tr[4*maxx];

void add(int x, int v){
	while(x < maxx){
		tr[x] += v;
		x += (x & -x);
	}
}

void add(int l, int r, int v){
//		cout << l << " " << r << " " << v << "done\n";
	if(l > r)
		swap(l, r);
	add(l, v);
	add(r+1, -v);
}
int sum(int x){
	int s = 0;
	while(x > 0){
		s += tr[x];
		x -= (x & -x);
	}
	return s;
}
int a[maxx];
void S()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		if(i > 1)
			add(a[i-1],a[i], 1);
	}
	for(int i = 0; i < m; i ++){
		int x;
		cin >> x;
		if(x == 1){
			int c, b;
			cin >> c >> b;
			if(c > 1){
				add(a[c-1], a[c], -1);
				add(a[c-1], b, 1);
			}
			if(c < n){
				add(a[c], a[c+1], -1);
				add(b, a[c+1], 1);
			}
			a[c] = b;
		}
		else{
			int b;
			cin >> b;
			cout << sum(b) << "\n";
		}
	}
/*	for(int i = 0; i <= 5; i ++)
		cout << sum(i) << " ";*/
}

int main()
{
	IOS;
	/*int t;
	cin >> t;
	while(t --)*/
		S();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 4044 KB Output is correct
3 Correct 3 ms 4044 KB Output is correct
4 Correct 3 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 45 ms 1736 KB Output is correct
9 Correct 70 ms 6820 KB Output is correct
10 Correct 53 ms 6852 KB Output is correct
11 Correct 48 ms 1604 KB Output is correct
12 Correct 47 ms 2760 KB Output is correct
13 Correct 50 ms 2800 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 4044 KB Output is correct
3 Correct 3 ms 4044 KB Output is correct
4 Correct 3 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 45 ms 1736 KB Output is correct
9 Correct 70 ms 6820 KB Output is correct
10 Correct 53 ms 6852 KB Output is correct
11 Correct 48 ms 1604 KB Output is correct
12 Correct 47 ms 2760 KB Output is correct
13 Correct 50 ms 2800 KB Output is correct
14 Correct 72 ms 6776 KB Output is correct
15 Correct 72 ms 6760 KB Output is correct
16 Correct 75 ms 6864 KB Output is correct
17 Correct 73 ms 6788 KB Output is correct
18 Correct 74 ms 6868 KB Output is correct