Advertisement
Guest User

dfdf

a guest
Oct 21st, 2019
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.53 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <set>
  5.  
  6. using namespace std;
  7. #define orid second.second
  8. #define li first
  9. #define ri second.first
  10. typedef long long laf;
  11. set<pair<int, pair<int, int>>> lines; // <left,<right, num>>
  12. vector<pair<int, int>> originals;
  13. vector<bool> taken;
  14. int N; int M;
  15.  
  16. bool sol() {
  17.     auto line = lines.begin();
  18.     if ((*line).li > 0) {
  19.         return false;
  20.     }
  21.     while (line != lines.end()) {
  22.         auto beg = line;
  23.         auto longest = beg;
  24.         while (beg != lines.end() && (*beg).li == (*line).li) {
  25.             if ((*beg).ri > (*longest).ri) { // Take interval starting in line.first with max line.second (long boi)
  26.                 longest = beg;
  27.             }
  28.             beg++;
  29.         }
  30.         beg = longest;
  31.         taken[(*longest).orid] = true;
  32.         if ((*longest).ri >= M) {
  33.             return true;
  34.         }
  35.         auto end = beg;
  36.         while (end != lines.end() && (*end).li < (*beg).ri + 1) {
  37.             // Find longest interval starting up to first moment after beg (last one to find new interval :(
  38.             if ((*end).ri > (*longest).ri) { // Take interval starting in line.first with max line.second (long boi)
  39.                 longest = end;
  40.             }
  41.             end++;
  42.         }
  43.         if (longest == beg) /* if we didn't find anything that went past beginning return 0 */ {
  44.             return false;
  45.         }
  46.         line = longest;
  47.     }
  48. }
  49.  
  50. int main() {
  51.     cin >> N;
  52.     for (int i = 0; i < N; ++i) {
  53.         cin >> M;
  54.         originals.clear();
  55.         taken.clear();
  56.         while (true) {
  57.             int L, R;
  58.             cin >> L >> R;
  59.             if (L == 0 && R == L) {
  60.                 break;
  61.             }
  62.             if (R < 0) {
  63.                 continue;
  64.             }
  65.             originals.emplace_back(L, R);
  66.             if (L < 0) {
  67.                 L = 0;
  68.             }
  69.             lines.emplace(L, make_pair(R, originals.size() - 1));
  70.         }
  71.         taken.resize(originals.size());
  72.         if (!sol()) {
  73.             cout << 0;
  74.             if (i < N - 1) {
  75.                 cout << endl;
  76.             }
  77.             continue;
  78.         };
  79.         int took = std::accumulate(taken.begin(), taken.end(), 0);
  80.         cout << took << endl;
  81.         for (int t = 0; t < taken.size(); t ++) {
  82.             if (taken[t]) {
  83.                 cout << originals[t].li << " " << originals[t].second << endl;
  84.             }
  85.         }
  86.         if (i < N - 1) {
  87.             cout << endl;
  88.         }
  89.     }
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement