Cod sursa(job #2724994)

Utilizator PetyAlexandru Peticaru Pety Data 18 martie 2021 11:22:19
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda simularesimulare Marime 2.45 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const int MAX = 3200;

ifstream fin ("cadrane.in");
ofstream fout ("cadrane.out");

int n, x[100002], y[100002], cp[100002], lazy[400002], aint[400002];

void push (int nod, int st, int dr) {
  if (lazy[nod] != 0) {
    aint[nod] += lazy[nod];
    if (st != dr) {
      lazy[2 * nod + 1] += lazy[nod];
      lazy[2 * nod] += lazy[nod];
    }
  }
  lazy[nod] = 0;
}

void update(int nod, int st, int dr, int a, int b, int val) {
  push(nod, st, dr);
  if (st > dr || st > b || dr < a)
    return;
  if (a <= st && dr <= b) {
    aint[nod] += val;
    if (st != dr) {
      lazy[2 * nod] += val;
      lazy[2 * nod + 1] += val;
    }
    return;
  }
  int mij = (st + dr) / 2;
  update(2 * nod, st, mij, a, b, val);
  update(2 * nod + 1, mij + 1, dr, a, b, val);
  aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
  return;
}
int ans;

void query (int nod, int st, int dr, int a, int b) {
  push(nod, st, dr);
  if (st > dr || st > b || dr < a)
    return;
  if (a <= st && dr <= b) {
    ans = min(ans, aint[nod]);
    return;
  }
  int mij = (st + dr) / 2;
  query(2 * nod, st, mij, a, b);
  query(2 * nod + 1, mij + 1, dr, a, b);
}

vector<int>lol[100002];

int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++) {
    fin >> x[i] >> y[i];
    cp[i] = x[i];
  }
  sort(cp + 1, cp + n + 1);
  int nrx = 0;
  for (int i = 1; i <= n; i++)
    if (i == 1 || cp[i] != cp[i - 1])
      cp[++nrx] = cp[i];
  for (int i = 1; i <= n; i++)
    x[i] = lower_bound(cp + 1, cp + nrx + 1, x[i]) - cp;
  for (int i = 1; i <= n; i++) {
    cp[i] = y[i];
  }
  sort(cp + 1, cp + n + 1);
  int nry = 0;
  for (int i = 1; i <= n; i++)
    if (i == 1 || cp[i] != cp[i - 1])
      cp[++nry] = cp[i];
  for (int i = 1; i <= n; i++)
    y[i] = lower_bound(cp + 1, cp + nry + 1, y[i]) - cp;
  for (int i = 1; i <= n; i++) {
    lol[x[i]].push_back(y[i]);
  }
  for (int i = 1; i <= nrx; i++)
    for (auto it : lol[i])
      update(1, 1, nry, 1, it, 1);
  int solution = 0;
  for (int i = 1; i <= nrx; i++) {
    if (i > 1) {
      for (auto it : lol[i - 1])
        update(1, 1, nry, 1, it, -1);
    }
    for (auto it : lol[i])
      update(1, 1, nry, it, nry, 1);
    ans = INF;
    query(1, 1, nry, 1, nry);
    solution = max(solution, ans);
  }
  fout << solution;
  return 0;
}