6096 2023. 10. 29 18:21:40 Gervid Zsonglőrködés cpp17 Elfogadva 100/100 477ms 82584 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1816 KiB
2 Elfogadva 3ms 2048 KiB
subtask2 20/20
3 Elfogadva 6ms 3072 KiB
4 Elfogadva 122ms 25652 KiB
5 Elfogadva 338ms 60992 KiB
6 Elfogadva 416ms 72888 KiB
7 Elfogadva 439ms 81116 KiB
8 Elfogadva 439ms 81392 KiB
9 Elfogadva 470ms 81112 KiB
10 Elfogadva 472ms 81404 KiB
11 Elfogadva 437ms 81724 KiB
subtask3 35/35
12 Elfogadva 3ms 3860 KiB
13 Elfogadva 3ms 3836 KiB
14 Elfogadva 3ms 3940 KiB
15 Elfogadva 3ms 4132 KiB
16 Elfogadva 3ms 4176 KiB
17 Elfogadva 4ms 4208 KiB
18 Elfogadva 3ms 4428 KiB
19 Elfogadva 4ms 4512 KiB
20 Elfogadva 4ms 4356 KiB
subtask4 45/45
21 Elfogadva 6ms 5032 KiB
22 Elfogadva 64ms 5856 KiB
23 Elfogadva 344ms 62824 KiB
24 Elfogadva 188ms 8972 KiB
25 Elfogadva 477ms 82376 KiB
26 Elfogadva 210ms 9376 KiB
27 Elfogadva 441ms 82516 KiB
28 Elfogadva 209ms 9588 KiB
29 Elfogadva 441ms 82584 KiB