Advertisement
limimage

H

Mar 29th, 2020
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.41 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define endl "\n"
  4. using namespace std;
  5. using ll = long long;
  6. using ld = long double;
  7. using pii = pair<int, int>;
  8.  
  9. constexpr int N = 2e5 + 5;
  10.  
  11. int t, n, m;
  12.  
  13. vector<int> start, fin;
  14. vector<int> num;
  15.  
  16. void Solve() {
  17. cin >> n >> m;
  18. num.resize(n + 1);
  19. for (int i = 0, a, b; i < m; i++) {
  20. cin >> a >> b;
  21. if (a > b) {
  22. start.push_back(b);
  23. fin.push_back(a);
  24. }
  25. }
  26. sort(start.begin(), start.end());
  27. sort(fin.begin(), fin.end());
  28. int cur = 0, si = 0, fi = 0;
  29. for (int i = 1; i <= n; i++) {
  30. while(si < m && start[si] == i)
  31. cur++, si++;
  32. num[i] = cur;
  33. while(fi < m && fin[fi] == i)
  34. cur--, fi++;
  35. }
  36. int val = *max_element(num.begin(), num.end());
  37. if (val != m - n + 2) {
  38. cout << 0 << endl;
  39. }
  40. else {
  41. vector<int> ans;
  42. for (int i = 1; i <= n; i++)
  43. if (num[i] == val)
  44. ans.push_back(i);
  45. cout << ans.size() << " ";
  46. for (int v: ans)
  47. cout << v << " ";
  48. cout << endl;
  49. }
  50. start.clear();
  51. fin.clear();
  52. num.clear();
  53. }
  54.  
  55. int main() {
  56. ios::sync_with_stdio(false);
  57. cin.tie(nullptr);
  58. cout.tie(nullptr);
  59. cin >> t;
  60. while(t--)
  61. //auto start = chrono::high_resolution_clock::now();
  62. Solve();
  63. //auto end = chrono::high_resolution_clock::now();
  64. //cout << endl << (chrono::duration_cast<chrono::duration<double>>(end - start)).count();
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement