|
|
back to boardTle test 13 with O(n) 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) 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) 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". |
|
|