Cod sursa(job #1414816)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 3 aprilie 2015 02:44:35
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100050

int N, X, L;
int A[MAXN];
int B[MAXN];
int C[MAXN];
priority_queue<int> S;

bool cmp(int a, int b) {
	if (A[a] != A[b]) {
		return A[a] < A[b];
	}
	return B[a] < B[b];
}

int main() {
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out","w", stdout);
	
	scanf("%d %d %d", &N, &X, &L);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &A[i], &B[i]);
		C[i] = i;
	}
	sort(C, C + N, cmp);
	
	int i = 0;
	int rem = X % L;
	long long ans = 0;
	int prvUpper = -1;
	while (i < N && A[ C[i] ] <= X) {
		int upper;
		if (A[ C[i] ] <= rem) {
			upper = rem;
		}
		else {
			int d = (A[ C[i] ] - rem + L - 1) / L;
			upper = rem + d * L;
		}
		
		while (!S.empty() && upper - L > prvUpper) {
			ans += S.top();
			S.pop();
			prvUpper += L;
		}
		
		while (i < N && A[ C[i] ] <= upper) {
			S.push(B[ C[i] ]);
			i++;
		}
		
		if (!S.empty()) {
			ans += S.top();
			S.pop();
		}
		
		prvUpper = upper;
	}
	
	printf("%lld\n", ans);
	
	return 0;
}