Cod sursa(job #2929183)

Utilizator lucafecheteFechete Luca Andrei lucafechete Data 25 octombrie 2022 00:51:34
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct concert {
	int beg;
	int end;

	concert()
	{
		beg = 0;
		end = 0;
	}

	void afisare()
	{
		cout << beg << " " << end << endl;
	}

}v[100001];

struct position {
	int indice;
	int suma;

	position()
	{
		indice = 0;
		suma = 0;
	}

	void afisare()
	{
		cout << indice << " " << suma << endl;
	}

}poz[100001];

bool compare(concert a, concert b)
{
	if (a.end < b.end)
		return 1;
	else if (a.end == b.end)
		if (a.beg < b.beg)
			return 1;
	return 0;
}

int main()
{
	int n;
	fin >> n;

	for (int i{ 1 }; i <= n; i++)
		fin >> v[i].beg >> v[i].end;

	sort(v + 1, v + n + 1, compare);

	int sum = 0, m = 0;
	
	for (int i = 1; i <= n; i++)
		if (v[i].beg >= v[poz[m].indice].end)
		{
			m++;
			sum += (v[i].end - v[i].beg);
			poz[m].indice = i;
			poz[m].suma = sum;
		}
		else
		{
			for (int j = 0; j < m; j++)
				if (v[i].beg <= v[poz[j + 1].indice].beg && v[i].beg >= v[poz[j].indice].end && (v[i].end - v[i].beg) >= poz[j + 1].suma)
				{
					sum += ((v[i].end - v[i].beg) - (poz[m].suma - poz[j].suma));
					m = j + 1;
					poz[m].indice = i;
					poz[m].suma = sum;
					break;
				}
		}

	fout << sum;
	return 0;
}





/* int poz = 0, sum = 0, prev = 0;
	for (int i{ 1 }; i <= n; i++)
		if (v[i].beg >= v[poz].end)
		{
			sum += (v[i].end - v[i].beg);
			prev = poz;
			poz = i;
		}
		else if (v[i].beg >= v[prev].end && (v[i].end - v[i].beg) > (v[poz].end - v[poz].beg))
		{
			sum += ((v[i].end - v[i].beg) - (v[poz].end - v[poz].beg));
			poz = i;
		}
	cout << sum;
*/