Cod sursa(job #1758930)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 18 septembrie 2016 08:49:15
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <cstdio>
#include <cctype>
#include <utility>
#include <algorithm>

#define x first
#define y second

#define BUF_SIZE 1<<17
#define MAXN 100000

std::pair <int, int> h[MAXN+1], v[MAXN+1];

int st[MAXN+1];

int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;

inline char nextch(){
    if(pos==BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos=0;
    return buf[pos++];
}

inline int read(){
    int x=0;
    char ch=nextch();
    while(!isdigit(ch)) ch=nextch();
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x;
}

int main(){
    int t, V, H, vf, i, ans, y;
    FILE *fout;
    fin=fopen("hvrays.in", "r");
    fout=fopen("hvrays.out", "w");
    for(t=read(); t; t--){
        H=read();
        V=read();
        for(i=1; i<=H; i++){
            h[i].x=read();
            h[i].y=read();
        }
        for(i=1; i<=V; i++){
            v[i].x=read();
            v[i].y=read();
        }
        std::sort(h+1, h+H+1);
        std::sort(v+1, v+V+1);
        vf=0;
        for(i=1; i<=H; i++){
            while((vf>0)&&(h[i].y>=h[st[vf]].y)) vf--;
            st[++vf]=i;
        }
        ans=0;
        i=V;
        while(vf>0){
            y=-1;
            while(h[st[vf]].x<=v[i].x){
                if(v[i].y>y) y=v[i].y;
                i--;
            }
            ans++;
            while((vf>0)&&(h[st[vf]].y<=y)) vf--;
        }
        fprintf(fout, "%d\n", ans);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}