Cod sursa(job #206576)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 7 septembrie 2008 20:32:43
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

#define maxl 100010

using namespace std;

long i, j, k, n, t, H, V, val, gas;
long h[2][maxl], v[2][maxl];
long p[maxl], q[maxl];
char cit[30];

/*void solve() {
    while (t > 0) {
        --t;
        scanf("%ld %ld\n", &H, &V);
        for (i = 1; i <= H; ++i) {
            scanf("%ld %ld", &h[0][i], &h[1][i]);
            p[i] = i;
		}

        for (i = 1; i <= V; ++i) {
            scanf("%ld %ld", &v[0][i], &v[1][i]);
            q[i] = i;
        }
        
        sort(p + 1,p + H + 1, cmp);
        sort(q + 1, q + V + 1, cmp2);
        
        j = V; 
		k = 0; 
		val = -1;
        for (i = H; i >= 1; --i) {
			if (h[1][p[i]] > val) {
				gas = 0;
				while (v[0][q[j]] >= h[0][p[i]] && j > 0) {
					  if (v[1][q[j]] > val) val = v[1][q[j]];
					  --j;
					  gas = 1;
				}
				if (gas > 0) {
					++k;
				}
			}
		}
        printf("%ld\n",k);
    }	
}*/

int cmp(long x, long y) {
    return h[0][x] < h[0][y];
}
int cmp2(long x, long y) {
    return v[0][x] < v[0][y];
}

int main() {
    freopen("hvrays.in","r",stdin);
    freopen("hvrays.out","w",stdout);
    scanf("%ld", &t);
	//solve();
    while (t > 0) {
        --t;
        scanf("%ld %ld\n", &H, &V);
        for (i = 1; i <= H; ++i) {
            scanf("%ld %ld", &h[0][i], &h[1][i]);
            p[i] = i;
		}

        for (i = 1; i <= V; ++i) {
            scanf("%ld %ld", &v[0][i], &v[1][i]);
            q[i] = i;
        }
        
        sort(p + 1,p + H + 1, cmp);
        sort(q + 1, q + V + 1, cmp2);
        
        j = V; 
		k = 0; 
		val = 1;
        for (i = H; i >= 1; --i) {
			if (h[1][p[i]] > val) {
				gas = 0;
				while (v[0][q[j]] >= h[0][p[i]] && j > 0) {
					  if (v[1][q[j]] > val) val = v[1][q[j]];
					  --j;
					  gas = 1;
				}
				if (gas > 0) {
					++k;
				}
			}
		}
        printf("%ld\n",k);
    }	
	
    while (t > 0) {
        --t;
        scanf("%ld %ld\n", &H, &V);
        for (i = 1; i <= H; ++i) {
            scanf("%ld %ld", &h[0][i], &h[1][i]);
            p[i] = i;
		}

        for (i = 1; i <= V; ++i) {
            scanf("%ld %ld", &v[0][i], &v[1][i]);
            q[i] = i;
        }
        
        sort(p + 1,p + H + 1, cmp);
        sort(q + 1, q + V + 1, cmp2);
        
        j = V; 
		k = 0; 
		val = -1;
        for (i = H; i >= 1; --i) {
			if (h[1][p[i]] > val) {
				gas = 0;
				while (v[0][q[j]] >= h[0][p[i]] && j > 0) {
					  if (v[1][q[j]] > val) val = v[1][q[j]];
					  --j;
					  gas = 1;
				}
				if (gas > 0) {
					++k;
				}
			}
		}
        printf("%ld\n", k);
    }
    
    return 0;    
}