https://www.acmicpc.net/problem/1946

Memo

시간초과를 주의합시당..

Code

제출 날짜

2021/05/01

메모리

3704 KB

시간

532 ms

#include <algorithm>
#include <iostream>
#include <vector>

int T, N;
std::vector<std::pair<int, int>> tcase;
std::vector<int> result;

void output()
{
	for(auto& i : result)
		std::cout << i << '\\n';
}

bool comp(std::pair<int, int> &a, std::pair<int, int> &b)
{
	if (a.first == b.first)
		return a.second < b.second;
	return a.first < b.first;
}

void solution()
{
	auto cnt = N, m = N;

	std::sort(tcase.begin(), tcase.end(), comp);
	for (auto i = 1; i < N; ++i)
	{
		m = std::min(m, tcase[i - 1].second);
		if (m < tcase[i].second)
			--cnt;
	}
	result.push_back(cnt);
}

void input()
{
	std::cin >> T;
	while (T--)
	{
		std::cin >> N;
		tcase = std::vector(N, std::pair<int, int>());
		for (auto &i : tcase)
			std::cin >> i.first >> i.second;
		solution();
	}
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input();
	output();
}

틀린코드 ㅜㅜ (시간초과..)

#include <algorithm>
#include <iostream>
#include <vector>

int T, N;
std::vector<std::pair<int, int>> tcase;
std::vector<int> result;

void output()
{
	for(auto& i : result)
		std::cout << i << '\\n';
}

bool comp(std::pair<int, int> &a, std::pair<int, int> &b)
{
	if (a.first == b.first)
		return a.second < b.second;
	return a.first < b.first;
}

void solution()
{
	int cnt = 1;

	std::sort(tcase.begin(), tcase.end(), comp);
	for (int i = 1; i < N; ++i)
	{
		auto tmp = std::max_element(tcase.begin(), tcase.begin() + i, [](const auto &lhs, const auto &rhs) {return lhs.second > rhs.second;});
		if ((*tmp).second > tcase[i].second)
			++cnt;
	}
	result.push_back(cnt);
}

void input()
{
	std::cin >> T;
	while (T--)
	{
		std::cin >> N;
		tcase = std::vector(N, std::pair<int, int>());
		for (auto &i : tcase)
			std::cin >> i.first >> i.second;
		solution();
	}
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input();
	output();
}