Cod sursă (job #733441)

#include <algorithm>
#include <stdio.h>
#include <queue>

struct Ghiseu {
	int left, right, no;
};


const char inputUrl[] = "stampile.in";
const char outputUrl[] = "stampile.out";
const int MAX = 2e5;

Ghiseu ghiseu[MAX];

struct elGhiseu {
	int x;

	bool operator<(const elGhiseu& A) const {
		return ghiseu[x].right < ghiseu[A.x].right;
	}
};


std::priority_queue<elGhiseu> q;
int v[MAX + 1], n, m;

int poz;
void addNextGhisee(const int& P) {
	while(poz < m && P >= ghiseu[poz].left) {
		q.push({poz});
		++poz;
	}
}

int ans;
int s[MAX + 1];
int S[MAX + 1];
void solve() {
	std::sort(ghiseu, ghiseu + m, [](const Ghiseu& A, const Ghiseu& B) {
			if(A.left == B.left)
				return A.right > B.right;
			return A.left < B.left;
		} );

	Ghiseu cur;
	for(int i = 1; i <= n; i++) {
		addNextGhisee(i);

		s[i] += s[i - 1];
		while(s[i] < v[i] && !q.empty()) {
			int P = q.top().x;
			S[ghiseu[P].left] += 1;
			S[ghiseu[P].right + 1] -= 1;
			if(s[i] + ghiseu[P].no <= v[i]) {
				s[i] += ghiseu[P].no;
				s[ghiseu[P].right + 1] -= ghiseu[P].no;
				ans += ghiseu[P].no;
				q.pop();
			} else {
				int cat = v[i] - s[i];
				s[i] += cat;
				ghiseu[P].no -= cat;
				ans += cat;
				s[ghiseu[P].right + 1] -= cat;
			}
		}

		if(s[i] < v[i]) {
			i = n + 1;
			ans = -1;
		}
	}
	for(int i = 1; i <= n; i++) {
		S[i] += S[i - 1];
		if(S[i] < v[i])
			ans = -1;
	}
}

void readInput() {
	FILE *fin = fopen(inputUrl, "r");
	fscanf(fin, "%d %d", &n, &m);

	for(int i = 1; i <= n; i++)
		fscanf(fin, "%d", &v[i]);

	for(int i = 0; i < m; i++)
		fscanf(fin, "%d %d %d", &ghiseu[i].left, &ghiseu[i].right, &ghiseu[i].no);

	fclose(fin);
}

void printAns() {
	FILE *fout = fopen(outputUrl, "w");

	fprintf(fout, "%d\n", ans);
	
	fclose(fout);
}

int main()
{
	readInput();
	solve();
	printAns();
	return 0;
}