Cod sursa(job #1558845)

Utilizator hrazvanHarsan Razvan hrazvan Data 29 decembrie 2015 17:34:13
Problema Cadrane Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <stdio.h>
#define MAXN 100000
#define INF 2000000000
typedef struct{
  int x, y;
}point;
point v[MAXN];
int pt1[MAXN], pt2[MAXN], pt[MAXN], cv[MAXN], pst[MAXN], pdr[MAXN];
int arb[4 * MAXN], ard[4 * MAXN];

inline int max2(int a, int b){
  return a > b ? a : b;
}

inline int min2(int a, int b){
  return a < b ? a : b;
}

void qs1(int st, int dr){
  int i = st, j = dr, piv = v[pt1[(st + dr) / 2]].x, aux;
  while(i <= j){
    while(v[pt1[i]].x < piv)
      i++;
    while(v[pt1[j]].x > piv)
      j--;
    if(i <= j){
      aux = pt1[i];  pt1[i] = pt1[j];  pt1[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs1(st, j);
  if(i < dr)
    qs1(i, dr);
}

void qs2(int st, int dr){
  int i = st, j = dr, piv = v[pt2[(st + dr) / 2]].y, aux;
  while(i <= j){
    while(v[pt2[i]].y < piv)
      i++;
    while(v[pt2[j]].y > piv)
      j--;
    if(i <= j){
      aux = pt2[i];  pt2[i] = pt2[j];  pt2[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs2(st, j);
  if(i < dr)
    qs2(i, dr);
}

inline void calc(int n){
  int st = -1, dr = 0, i;
  for(i = 0; i < n; i++){
    while(v[pt2[st + 1]].y < v[pt2[i]].y)
      st++;
    while(dr < n - 1 && v[pt2[dr + 1]].y == v[pt2[i]].y)
      dr++;
    pst[i] = st;
    pdr[i] = dr + 1;
  }
}

void adaug(int p, int st, int dr, int x, int y, int s){
  if(st >= x && dr <= y)
    ard[p] += s;
  else  if(st != dr){
    int m = (st + dr) / 2;
    ard[2 * p + 1] += ard[p];
    ard[2 * p + 2] += ard[p];
    ard[p] = 0;
    if(x <= m)
      adaug(2 * p + 1, st, m, x, y, s);
    if(y > m)
      adaug(2 * p + 2, m + 1, dr, x, y, s);
    arb[p] = min2(arb[2 * p + 1] + ard[2 * p + 1], arb[2 * p + 2] + ard[2 * p + 2]);
  }
}

void del(int p, int st, int dr, int q){
  if(st == dr){
    arb[q] = INF;
    ard[q] = 0;
  }
  else{
    int m = (st + dr) / 2;
    ard[2 * p + 1] += ard[p];
    ard[2 * p + 2] += ard[p];
    ard[p] = 0;
    if(q <= m)
      del(2 * p + 1, st, m, p);
    else
      del(2 * p + 2, m + 1, dr, p);
    arb[p] = min2(arb[2 * p + 1] + ard[2 * p + 1], arb[2 * p + 2] + ard[2 * p + 2]);
  }
}

inline void add(int n, int p, int s){
  adaug(0, 0, n - 1, p, n - 1, s);
}

int main(){
  FILE *in = fopen("cadrane.in", "r");
  int n, i;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%d%d", &v[i].x, &v[i].y);
    pt1[i] = pt2[i] = i;
  }
  fclose(in);
  qs1(0, n - 1);
  qs2(0, n - 1);
  calc(n);
  for(i = 0; i < n; i++)
    pt[pt2[i]] = i;
  for(i = 0; i < n; i++)
    adaug(0, 0, n - 1, pst[pt[i]] + 1, n - 1, 1);
  i = 0;
  int j, k, st = 0, max = -INF;
  max = max2(max, arb[0] + ard[0]);
  while(i < n){
    j = i;
    while(j < n && v[pt1[j]].x == v[pt1[i]].x)
      j++;
    for(k = st; k < i; k++){
      adaug(0, 0, n - 1, pst[pt[pt1[k]]] + 1, n - 1, -1);
      adaug(0, 0, n - 1, 0, pst[pt[pt1[k]]], 1);
    }
    st = i;
    i = j;
    max = max2(max, i - st + arb[0] + ard[0]);
  }
  FILE *out = fopen("cadrane.out", "w");
  fprintf(out, "%d", max);
  fclose(out);
  return 0;
}