Cod sursa(job #467510)

Utilizator crawlerPuni Andrei Paul crawler Data 29 iunie 2010 10:19:59
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define Nmax 100100

#define x first
#define y second

int n;
pair <int, int> a[Nmax];
vector<int> coord;

int sum[Nmax*3];    //pentru suma elementelor
int prefix[Nmax*3]; //pentru prefixul de suma minima

inline int Min(int A, int B) {
  return A < B ? A : B;
}

void update(int ind, int st, int dr, int poz, int val) {
  if (poz < st || poz > dr) 
    return ;
  if (st == dr) {
    sum[ind] += val;
    prefix[ind] = sum[ind];
    return ;
  }
  int mij = (st+dr)/2;
  if (poz <= mij)
    update(ind*2  , st, mij  , poz, val);
  else
    update(ind*2+1, mij+1, dr, poz, val);
    
  sum[ind] = sum[ind*2] + sum[ind*2+1];
  prefix[ind] = Min(prefix[ind*2], sum[ind*2] + prefix[ind*2+1]);
}

int main() {
  freopen("cadrane.in" , "r", stdin );
  freopen("cadrane.out", "w", stdout);

  scanf("%d", &n);

  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a[i].x, &a[i].y);
    coord.push_back(a[i].y);
  }
    
  //sortez punctele dupa x
  sort(a+1, a+n+1);

  //normalizez y-ul
  sort(coord.begin(), coord.end());
  coord.erase(unique(coord.begin(), coord.end()), coord.end());
  int N = coord.size();
  for (int i = 1; i <= n; ++i) {
    int Y = a[i].y;
    a[i].y = 0;
    for (int j = (1<<18); j > 0; j /= 2)
      if (a[i].y + j < (int)coord.size() && coord[a[i].y + j] <= Y)
        a[i].y += j;
    ++a[i].y;
  }

  //initializez arborele
  for (int i = 1; i <= n; ++i)
    update(1, 1, N, a[i].y + 1, -1);

  //parcurg punctele pe x si fac_updateuri pe arborele de intervale
  int last = 1, best = 0, pctA = n;

  for (int i = 1; i <= n; ++i) {
    last = i;

    while (last < n && a[last+1].x == a[i].x)
      ++last;

    //astea ajung pe axa si nu le mai scad
    for (int j = i; j <= last; ++j) {
      update(1, 1, N, a[j].y + 1, +1);
    }

    if (best < pctA + prefix[1])
      best = pctA + prefix[1];

    //acum astea sunt dupa axa si le adun
    for (int j = i; j <= last; ++j) {
      update(1, 1, N, a[j].y, +1);
      --pctA;
    }

    i = last;
  }

  printf("%d\n", best);

  return 0;
}