ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1203. Scientific Conference

Tle test 13 with O(n)
Posted by Ghiorghiu Ioan-Viorel 26 Mar 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)
Posted by ToadMonster 26 Mar 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)
Posted by Noob 31 Mar 2017 03:34
Comparator must return false if a == b.
Re: Tle test 13 with O(n)
Posted by ToadMonster 31 Mar 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".