Cod sursa(job #1428862)

Utilizator hrazvanHarsan Razvan hrazvan Data 5 mai 2015 10:49:05
Problema Hvrays Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXL 200000
#define BUFF (1 << 22)
FILE *in;
int x[MAXL], y[MAXL], point[MAXL];
char tip[MAXL];
int p = BUFF;
char buff[BUFF];

inline char cif(char ch){
  if(ch >= '0' && ch <= '9')
    return 1;
  return 0;
}

inline char getch(){
  if(p == BUFF){
    fread(buff, 1, BUFF, in);
    p = 0;
  }
  p++;
  return buff[p - 1];
}

inline int getnum(){
  int rez = 0;
  char ch = getch();
  while(!cif(ch))
    ch = getch();
  while(cif(ch)){
    rez *= 10;
    rez += ch - '0';
    ch = getch();
  }
  return rez;
}

inline char cmp(int x1, int t1, int x2, int t2){
  if(x1 > x2)
    return 1;
  if(x2 > x1)
    return 0;
  if(t1 > t2)
    return 1;
  if(t2 > t1)
    return 0;
  return 0;
}

void qs(int st, int dr){
  int i = st, j = dr, m = st + rand() % (dr - st + 1), pivx = x[point[m]], pivt = tip[point[m]], aux;
  while(i <= j){
    while(cmp(x[point[i]], tip[point[i]], pivx, pivt))
      i++;
    while(cmp(pivx, pivt, x[point[j]], tip[point[j]]))
      j--;
    if(i <= j){
      aux = point[i];  point[i] = point[j];  point[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

int main(){
  srand(time(NULL));
  in = fopen("hvrays.in", "r");
  FILE *out = fopen("hvrays.out", "w");
  int t, h, v, i, l, hmcrt, hmpsb, rez;
  t = getnum();
  for(; t > 0; t--){
    h = getnum();
    v = getnum();
    for(i = 0; i < h; i++){
      x[i] = getnum();
      y[i] = getnum();
      tip[i] = 0;
      point[i] = i;
    }
    for(i = 0; i < v; i++){
      x[i + h] = getnum();
      y[i + h] = getnum();
      tip[i + h] = 1;
      point[i + h] = i + h;
    }
    l = h + v;
    qs(0, l - 1);
    rez = 0;
    hmcrt = hmpsb = -1;
    for(i = 0; i < l; i++){
      if(tip[point[i]] == 1 && hmpsb < y[point[i]])
        hmpsb = y[point[i]];
      if(tip[point[i]] == 0 && y[point[i]] > hmcrt){
        hmcrt = hmpsb;
        rez++;
      }
    }
    fprintf(out, "%d\n", rez);
  }
  fclose(in);
  fclose(out);
  return 0;
}