Cod sursa(job #1277686)

Utilizator evodaniVasile Daniel evodani Data 27 noiembrie 2014 23:46:28
Problema Arbori de intervale Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
using namespace std;
FILE *fin, *fout;

int T[240005];

void updateTree (int* T, int node, int l, int r, int pos, int val) {
	int m = (l+r) / 2;

	if (l == r)
		T[node] += val;
	else {
		if (pos <= m) updateTree (T, 2*node, l, m, pos, val);
		else updateTree (T, 2*node+1, m+1, r, pos, val);
		T[node] = T[2*node] + T[2*node+1];
	}
}

int queryTree (int* T, int node, int l, int r, int a, int b) {
	int m = (l+r)/2;
	int li = 0 ,ri = 0;

	if (l>=a && r <= b) return T[node];
	if (a<=m)  li = queryTree(T, node*2, l, m, a, b);
	if (b>m) ri = queryTree(T, node*2+1, m+1, r, a, b);

	return li+ri;
}

int searchK (int* T, int n, int sum) {
	int lk = 1, rk = n, mk, k = -1, intSum;

	while (lk <= rk) {
		mk = (lk+rk) / 2;
		intSum = queryTree(T, 1, 1, n, 1, mk);

		if (sum == intSum) {
			k = mk;
			rk = mk-1;
		} else
		if (intSum < sum)
			lk = mk+1;
		else // intSum > sum
			rk = mk-1;
	}

	return k;
}

int main() {
	fin = fopen ("aib.in", "r");
	fout = fopen ("aib.out", "w");

	int n, m, i, t, a, b;

	fscanf(fin, "%d%d", &n, &m);

	for (i=1; i<=n; ++i) {
		fscanf (fin, "%d", &a);
		updateTree(T, 1, 1, n, i, a);
	}

	for (i=1; i<=m; ++i) {
		fscanf (fin, "%d", &t);
		if (t==0) { //Add b to the a'th position
			fscanf (fin, "%d%d", &a, &b);
			updateTree(T, 1, 1, n, a, b);
		} else
		if (t==1) { //Get sum [a, b]
			fscanf (fin, "%d%d", &a, &b);
			fprintf(fout, "%d\n", queryTree(T, 1, 1, n, a, b));
		}
		else { //Get k s.t. sum [1, k] == a
			fscanf (fin, "%d", &a);
			fprintf (fout, "%d\n", searchK(T, n, a));
		}
	}

	fclose(fin); fclose(fout);
	return 0;
}