Submission #475152

#	Time	Username	Problem	Language	Result	Execution time	Memory
475152		ismoilov	Simple game (IZhO17_game)	C++14	100 / 100	75 ms	6868 KiB

game

#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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51