Solution UVA: 10020 - Minimal coverage

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10020 - Minimal coverage	Accepted	C++11	0.040	0.000	1779	3 mins ago

#include<bits/stdc++.h>

#define N 1000111

#define L first

#define R second

using namespace std;

int t, m, l, r;

typedef pair<int, int> ii;

       

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> t;

    while(t--){

        cin >> m;  

       

        priority_queue<ii, vector<ii>, greater<ii>> seg;

        while(cin >> l >> r){

            if (l==0 && r==0) break;

            seg.push({l,r});

        }

   

        vector<ii> res;

        l= 0, r=0;

        bool loop;

        do{

            loop= false;

            int have= -1000111000;

            while(!seg.empty()){

                ii p= seg.top();

                if (p.L <= l && p.R > r) r= p.R, have= p.L;

                if (p.L > l) break;

                loop= true;

                seg.pop();

            }

            if (have!=-1000111000) res.push_back({have, r});

            l=r;

        }while(loop==true && r<m);

       

        if (r<m) cout<<"0\n";

        else{

            cout<<res.size()<<"\n";

            for(auto p:res) cout<<p.L<<" "<<p.R<<"\n";

        }

        if (t) cout<<"\n";

    }

}