ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1203. Научная конференция

Tle test 13 with O(n)
Послано Ghiorghiu Ioan-Viorel 26 мар 2017 07:11
Hi, I get tle on test thirteen, but i can't find out what I'm doing wrong. Thank you for helping me!
#include <iostream>
#include <algorithm>
#define DM 100000

using namespace std;

int n, k, m;
pair <int, int> x[DM], a, b;

bool cmp(pair<int,int> a, pair<int,int> b)
{
    if (a.second > b.second)
        return 0;
    return 1;
}

int main()
{
    cin >> n;
    for (; k < n; ++k)
        cin >> x[k].first >> x[k].second;
    sort (x, x + n, cmp);
    k = 1;
    m = x[0].second;
    for (int i = 1; i < n; ++i)
    {
        if (x[i].first > m)
        {
            m = x[i].second;
            ++k;
        }
    }
    cout << k;
    return 0;
}
Re: Tle test 13 with O(n)
Послано ToadMonster 26 мар 2017 12:53
GCC iostreams are slow by default.

Try VS compiler for your code.
Or put "std::ios::sync_with_stdio(false);" line in the very beginning of main()
Re: Tle test 13 with O(n)
Послано Noob 31 мар 2017 03:34
Comparator must return false if a == b.
Re: Tle test 13 with O(n)
Послано ToadMonster 31 мар 2017 10:19
Comparator is wrong at all.

Code after sort hopes data is sorted by end time in ascending order.
So comparator should look like "a.second < b.second".