Cod sursa(job #1885604)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 20 februarie 2017 09:29:47
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 100050
#define DIM 1000000

using namespace std;

struct coord
{
    int x, y;
    bool operator>(const coord &e) const
    {
        return y > e.y;
    }
};
int t, h, v;
coord hes[MAXN], ves[MAXN];

char buf[DIM];
int cursor;

inline void adv()
{
    if (++cursor == DIM)
    {
        cursor = 0;
        fread(buf, DIM, 1, stdin);
    }
}

int getInt()
{
    for (cursor; !isdigit(buf[cursor]); adv());
    int nr = 0;
    for (cursor; isdigit(buf[cursor]); adv())
        nr = nr*10 + buf[cursor] - '0';
    return nr;
}

void read()
{
    h = getInt();
    v = getInt();
    for (int i = 1; i <= h; i++) {
        hes[i].x = getInt();
        hes[i].y = getInt();
    }
    for (int i = 1; i <= v; i++) {
        ves[i].x = getInt();
        ves[i].y = getInt();
    }
}

void solve()
{
    sort(hes+1, hes+h+1, greater<coord>());
    sort(ves+1, ves+v+1, greater<coord>());
    int xmax = -1, xcrt = -1, sol = 0;
    for (int i = 1, j = 1; i <= h; i++)
    {
        for (j; j <= v && ves[j].y >= hes[i].y; j++)
            xmax = max(xmax, ves[j].x);
        if (hes[i].x > xcrt) {
            sol++;
            xcrt = xmax;
        }
    }
    printf("%d\n", sol);
}

int main()
{
    freopen("hvrays.in", "r", stdin);
    freopen("hvrays.out", "w", stdout);
    fread(buf, DIM, 1, stdin);

    t = getInt();
    while (t--) {
        read();
        solve();
    }

    return 0;
}