NOIC - Ideia 01 - Exemplo 2

noic-ideia01-ex02.cpp

// NOIC - Ideia 1
// Exemplo 2
// Complexidade: O(K log M)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

typedef pair<int, int> pii;

int soma[maxn];

int main(void)
{
	int n, m, k;
	cin >> n >> m >> k;

	vector<pii> C;

	for (int j = 1; j <= m; j++)
	{
		int i, x;
		cin >> i >> x;

		C.push_back({i, x}); // inserimos cada par em C
	}

	soma[0] = 0; // caso base
	for (int i = 1; i <= m; i++)
		soma[i] = soma[i-1] + C[i-1].second; // calculamos a soma de prefixos

	for (int i = 1; i <= k; i++)
	{
		int l, r;
		cin >> l >> r;

		// a função lower bound do C++ realiza uma busca binária
		// ela retorna a primeira posição em um vetor ordenado que tem valor maior ou igual a um certo parâmetro dado
		// no caso, queremos a primeira posição em C cujo índice no par é maior ou igual a l
		// por isso usamos o par {l, 0}
		int a = (int)(lower_bound(C.begin(), C.end(), make_pair(l, 0))-C.begin());

		// fazemos o mesmo pra posição b, nesse caso para achar a última posição menor
		// ou igual a r encontramos a primeira maior ou igual a r+1 e subtraímos 1 dela 
		int b = (int)(lower_bound(C.begin(), C.end(), make_pair(r+1, 0))-C.begin()-1);

		a++, b++; // como C é 0-indexado, aumentamos 1 em a e b

		if (a > b) cout << "0\n"; // se a >= b, todos os números em [l...r] são iguais a 0
		else cout << soma[b]-soma[a-1] << "\n"; // soma em [a...b]
	}
}