60962023-10-29 18:21:40GervidZsonglőrködéscpp17Elfogadva 100/100477ms82584 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
    int n, i, j = 0, k, out = 0, temp;
    cin >> n;

	vector<pair<int, int>> intervals(n); //fordított sorrendben experimenting
	map<int, vector<int>> startsat;

	for (i = 0; i < n; i++)
	{
		cin >> intervals[i].second >> intervals[i].first;
	}

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

	for (i = 0; i < n; i++)
	{
		if (startsat.count(intervals[i].second) == 0)
		{
			startsat[intervals[i].second] = { i };
		}
		else
		{
			startsat[intervals[i].second].push_back(i);
		}
	}

	for (i = 0; i < n; i++)
	{
		out++;

		while (intervals[j].second == -1)
		{
			j++;
		}
		intervals[j].second = -1;
		k = intervals[j].first;

		while (startsat[k].size() > 0)
		{
			temp = k;
			k = intervals[startsat[temp].back()].first;
			intervals[startsat[temp].back()].second = -1;
			startsat[temp].pop_back();
			i++;
		}
	}

	cout << out;
}
//4
//4 9
//2 4
//9 12
//1 4
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1816 KiB
2Elfogadva3ms2048 KiB
subtask220/20
3Elfogadva6ms3072 KiB
4Elfogadva122ms25652 KiB
5Elfogadva338ms60992 KiB
6Elfogadva416ms72888 KiB
7Elfogadva439ms81116 KiB
8Elfogadva439ms81392 KiB
9Elfogadva470ms81112 KiB
10Elfogadva472ms81404 KiB
11Elfogadva437ms81724 KiB
subtask335/35
12Elfogadva3ms3860 KiB
13Elfogadva3ms3836 KiB
14Elfogadva3ms3940 KiB
15Elfogadva3ms4132 KiB
16Elfogadva3ms4176 KiB
17Elfogadva4ms4208 KiB
18Elfogadva3ms4428 KiB
19Elfogadva4ms4512 KiB
20Elfogadva4ms4356 KiB
subtask445/45
21Elfogadva6ms5032 KiB
22Elfogadva64ms5856 KiB
23Elfogadva344ms62824 KiB
24Elfogadva188ms8972 KiB
25Elfogadva477ms82376 KiB
26Elfogadva210ms9376 KiB
27Elfogadva441ms82516 KiB
28Elfogadva209ms9588 KiB
29Elfogadva441ms82584 KiB