Cod sursa(job #2377865)

Utilizator memecoinMeme Coin memecoin Data 11 martie 2019 11:52:24
Problema Reconst Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string.h> 
#include <map>

using namespace std;

ifstream fin("reconst.in");
ofstream fout("reconst.out");

#define MAXN 2048

struct update {
	int start;
	int end;
	int value;

	bool operator<(const update &rhs) const { 
		if (start == rhs.start) {
			return end < rhs.end;
		}

		return start < rhs.start ; 
	}
};

int n, m;

vector<update> updates;

map<int, vector<update>> startingAt;

int minIt;
int maxIt;

void split(update &x, update &y) {
	if (x.end == y.end) {
		return;
	}

	startingAt[x.end + 1].push_back({ x.end + 1, y.end, y.value - x.value });
}

int endResult[MAXN];

int main() {

	fin >> n >> m;

	for (int i = 0; i < m; ++i) {
		int s, e, v;
		fin >> s >> e >> v;
		update u = { s,e,v };
		
		minIt = min(minIt, s);
		maxIt = max(maxIt, e);

		startingAt[s].push_back(u);
	}

	for (int i = minIt; i <= maxIt; ++i) {
		sort(startingAt[i].begin(), startingAt[i].end());

		if (startingAt[i].size() == 0) {
			continue;
		}
		
		if (startingAt[i].size() >= 2) {
			auto first = startingAt[i][0];
			for (int j = 1; j < startingAt[i].size(); ++j) {
				auto second = startingAt[i][j];
				split(first, second);
			}
		}

		updates.push_back(startingAt[i][0]);
	}

	sort(updates.begin(), updates.end());

	for (int i = updates.size() - 1; i >= 0; i--) {
		int s = 0;
		for (int j = updates[i].start + 1; j <= updates[i].end; ++j) {
			s += endResult[j];
		}

		endResult[updates[i].start] = updates[i].value - s;
	}

	for (int i = 1; i <= n; ++i) {
		fout << endResult[i] << " ";
	}

	return 0;
}