oj.uz

Submission #48394

# Submission time Handle Problem Language Result Execution time Memory
48394 2018-05-12T17:06:45 Z aleksami Simple game (IZhO17_game) C++14
0 / 100
 3 ms 872 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 3 ms 872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 3 ms 872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 3 ms 872 KB Output isn't correct
3 Halted 0 ms 0 KB -