Cod sursa(job #90784)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 10 octombrie 2007 13:32:44
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 100010
#define pb push_back
#define mp make_pair
#define f first
#define s second

vector<pair<int,int> > H, V, h;
int N, M, Case, Right[NMAX], S[NMAX];

int main()
{
        int i, j, num, xmax, ns=0, x, y;

//        freopen("h.in", "r", stdin);
//        freopen("h.out", "w", stdout);
        scanf("%d", &Case);

        while (Case--)
        {
                xmax = ns = 0;
                memset(S,0,sizeof(S));
                memset(Right,0,sizeof(Right));
                V.clear(); H.clear(); h.clear();
                scanf("%d%d", &N, &M);
                for (i = 0; i < N; i++)
                    scanf("%d%d", &x, &y), H.pb(mp(-y,x)), h.pb(mp(x,y));
                for (i = 0; i < M; i++)
                    scanf("%d%d", &x, &y), V.pb(mp(-y,x));

                sort(h.begin(), h.end());
                sort(V.begin(), V.end());
                sort(H.begin(), H.end());
                for (i = 0; i < M; i++) V[i].f = -V[i].f;
                for (i = 0; i < N; i++) H[i].f = -H[i].f;
        
                for (i = j = 0; i < N; i++)
                {
                        xmax = 0, x = -1;
                        while (V[j].f>=H[i].f && j < M)
                        {
                                if (V[j].s >= H[i].s && xmax < V[j].s)
                                   xmax = V[j].s, x = j;
                                j++;
                        }
                        if (i>0)
                        {
                           Right[i] = Right[i-1];
                           if (x>=0 && V[x].s > V[ Right[i-1] ].s)
                              Right[i] = x;
                        }
                        else Right[i] = x;
                }
        
                for (i = 0; i < N; i++)
                        if (Right[i] >= 0)
                            if ((ns==0) || (V[ S[ns-1] ].s < H[i].s)) S[ns++] = Right[i];
                     
                printf("%d\n", ns);
        }
        
        return 0;
        
}