60962023-10-29 18:21:40GervidZsonglőrködéscpp17Accepted 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
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1816 KiB
2Accepted3ms2048 KiB
subtask220/20
3Accepted6ms3072 KiB
4Accepted122ms25652 KiB
5Accepted338ms60992 KiB
6Accepted416ms72888 KiB
7Accepted439ms81116 KiB
8Accepted439ms81392 KiB
9Accepted470ms81112 KiB
10Accepted472ms81404 KiB
11Accepted437ms81724 KiB
subtask335/35
12Accepted3ms3860 KiB
13Accepted3ms3836 KiB
14Accepted3ms3940 KiB
15Accepted3ms4132 KiB
16Accepted3ms4176 KiB
17Accepted4ms4208 KiB
18Accepted3ms4428 KiB
19Accepted4ms4512 KiB
20Accepted4ms4356 KiB
subtask445/45
21Accepted6ms5032 KiB
22Accepted64ms5856 KiB
23Accepted344ms62824 KiB
24Accepted188ms8972 KiB
25Accepted477ms82376 KiB
26Accepted210ms9376 KiB
27Accepted441ms82516 KiB
28Accepted209ms9588 KiB
29Accepted441ms82584 KiB