Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <numeric>
- #include <set>
- using namespace std;
- #define orid second.second
- #define li first
- #define ri second.first
- typedef long long laf;
- set<pair<int, pair<int, int>>> lines; // <left,<right, num>>
- vector<pair<int, int>> originals;
- vector<bool> taken;
- int N; int M;
- bool sol() {
- auto line = lines.begin();
- if ((*line).li > 0) {
- return false;
- }
- while (line != lines.end()) {
- auto beg = line;
- auto longest = beg;
- while (beg != lines.end() && (*beg).li == (*line).li) {
- if ((*beg).ri > (*longest).ri) { // Take interval starting in line.first with max line.second (long boi)
- longest = beg;
- }
- beg++;
- }
- beg = longest;
- taken[(*longest).orid] = true;
- if ((*longest).ri >= M) {
- return true;
- }
- auto end = beg;
- while (end != lines.end() && (*end).li < (*beg).ri + 1) {
- // Find longest interval starting up to first moment after beg (last one to find new interval :(
- if ((*end).ri > (*longest).ri) { // Take interval starting in line.first with max line.second (long boi)
- longest = end;
- }
- end++;
- }
- if (longest == beg) /* if we didn't find anything that went past beginning return 0 */ {
- return false;
- }
- line = longest;
- }
- }
- int main() {
- cin >> N;
- for (int i = 0; i < N; ++i) {
- cin >> M;
- originals.clear();
- taken.clear();
- while (true) {
- int L, R;
- cin >> L >> R;
- if (L == 0 && R == L) {
- break;
- }
- if (R < 0) {
- continue;
- }
- originals.emplace_back(L, R);
- if (L < 0) {
- L = 0;
- }
- lines.emplace(L, make_pair(R, originals.size() - 1));
- }
- taken.resize(originals.size());
- if (!sol()) {
- cout << 0;
- if (i < N - 1) {
- cout << endl;
- }
- continue;
- };
- int took = std::accumulate(taken.begin(), taken.end(), 0);
- cout << took << endl;
- for (int t = 0; t < taken.size(); t ++) {
- if (taken[t]) {
- cout << originals[t].li << " " << originals[t].second << endl;
- }
- }
- if (i < N - 1) {
- cout << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement