Cod sursa(job #1065839)

Utilizator misinozzz zzz misino Data 23 decembrie 2013 18:56:48
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second
#define N 100010
#define punct pair<int,int>
using namespace std;
ifstream f("hvrays.in");
ofstream g("hvrays.out");
int t,i,sol,h,v,p,cur,maxi;
punct vh[N],vv[N];
inline bool cmp(punct a,punct b)
{
    return a.y>b.y;
}
int main()
{
    f>>t;
    for(;t;--t)
    {
        f>>h>>v;
        for(i=1;i<=h;++i)
        f>>vh[i].x>>vh[i].y;
        for(i=1;i<=v;++i)
        f>>vv[i].x>>vv[i].y;
        sort(vh+1,vh+h+1,cmp);
        sort(vv+1,vv+v+1,cmp);
        p=1;
        cur=maxi=-1;
        sol=0;
        for(i=1;i<=h;++i)
        {
            while(p<=v&&vv[p].y>=vh[i].y)
            {
                maxi=max(maxi,vv[p].x);
                ++p;
            }
            if(cur<maxi)
            {
                cur=maxi;
                ++sol;
            }
        }
        g<<sol<<'\n';
    }
    return 0;
}