Cod sursa(job #2298171)

Utilizator livliviLivia Magureanu livlivi Data 7 decembrie 2018 17:23:05
Problema Arbori indexati binar Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
#define N 100000
#define d(x) x&(-x)
using namespace std;

ifstream cin("aib.in");
ofstream cout("aib.out");

int AIB[N + 1];
int v[N + 1];
int n;

void update(int p, int x){
	for(; p <= n; p += d(p))
		AIB[p] += x;
}

int query(int p){
	int sum = 0;

	for(; p > 0; p -= d(p))
		sum += AIB[p];

	return sum;
}

int cb(int x){
	int p = (1 << 17);
	int ans = 0;

	while(p > 0){
		if (ans + p <= n && AIB[ans + p] <= x){
			ans += p;
			x -= AIB[ans + p];
		}
		p /= 2;
	}

	if (x == 0) return ans;
	else return -1;
}

int main(){
	int m; cin >> n >> m;

	for(int i = 1; i <= n; i++){
		int x; cin >> x;
		update(i, x);
	}

	for(int i = 1; i <= m; i++){
		int op; cin >> op;

		if (op == 0){
			int a, b; cin >> a >> b;
			update(a, b);
		}
		else
		if (op == 1){
			int a, b; cin >> a >> b;
			cout << query(b) - query(a - 1) << '\n';
		}
		else {
			int a; cin >> a;
			cout << cb(a) << '\n';
		}
	}

	return 0;
}