제출 #48394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48394		aleksami	Simple game (IZhO17_game)	C++14	0 / 100	3 ms	872 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXH 1000005
int a[MAXN];
int bit[MAXH];

void update(int b[],int idx,int val)
{
	while(idx < MAXN)
	{
		b[idx]+=val;
		idx+=idx&(-idx);
	}
}
int get(int b[],int idx)
{
	int s=0;
	while(idx > 0)
	{
		s+=b[idx];
		idx-=idx&(-idx);
	}
	return s;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q;
	cin >> n >> q;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		update(bit,a[i],1);
	}
	while(q--)
	{
		int t;
		cin >> t;
		if(t==1)
		{
			int pos,val;
			cin >> pos >> val;
			pos--;
			update(bit,a[pos],-1);
			a[pos]=val;
			update(bit,a[pos],+1);
		}
		else
		{
			int h;
			cin >> h;
			cout << get(bit,h) << "\n";
		}
	}
	return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51