Cod sursa(job #2728068)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 22 martie 2021 19:21:08
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

struct SegTree {
  int Size;
  vector<int> tree, lazy;

  SegTree(int N) {
    Size = 1;
    while (Size < N)
      Size <<= 1;
    tree.resize(Size << 1 | 1), lazy.resize(Size << 1 | 1);
  }

  void propagate(int x, int lx, int rx) {
    if (lx == rx || lazy[x] == 0)
      return;
    for (int i = 0; i < 2; ++i)
      tree[x << 1 | i] += lazy[x], lazy[x << 1 | i] += lazy[x];
    lazy[x] = 0;
  }

  void update(int x, int lx, int rx, int st, int dr, int val) {
    propagate(x, lx, rx);
    if (st <= lx && rx <= dr) {
      tree[x] += val, lazy[x] += val;
      return;
    }
    int mid = (lx + rx) >> 1;
    if (st <= mid)
      update(x << 1, lx, mid, st, dr, val);
    if (mid < dr)
      update(x << 1 | 1, mid + 1, rx, st, dr, val);
    tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
  }
};

void max_self(int &a, int b) {
  a = max(a, b);
}

int main() {
  int N;
  fin >> N;
  vector<pair<int,int>> xs(N), ys(N);
  for (int i = 0; i < N; ++i) {
    int x, y;
    fin >> x >> y;
    xs[i] = make_pair(x, i);
    ys[i] = make_pair(y, i);
  }
  sort(xs.begin(), xs.end()), sort(ys.begin(), ys.end());
  int X = 1;
  vector<pair<int,int>> norm_coord(N);
  norm_coord[xs[0].second].first = 1;
  for (int i = 1; i < N; ++i) {
    if (xs[i].first != xs[i - 1].first)
      ++X;
    norm_coord[xs[i].second].first = X;
  }
  int Y = 1;
  norm_coord[ys[0].second].second = 1;
  for (int i = 1; i < N; ++i) {
    if (ys[i].first != ys[i - 1].first)
      ++Y;
    norm_coord[ys[i].second].second = Y;
  }
  vector<int> adj[X + 1];
  SegTree tree(Y);
  for (auto p : norm_coord) {
    adj[p.first].emplace_back(p.second);
    tree.update(1, 1, Y, 1, p.second, 1);
  }
  int ans = 0;
  for (int i = 1; i <= X; ++i) {
    if (i > 1)
      for (int y : adj[i - 1])
        tree.update(1, 1, Y, 1, y, -1);
    for (int y : adj[i])
      tree.update(1, 1, Y, y, Y, 1);
    max_self(ans, tree.tree[1]);
  }
  fout << ans << '\n';
  return 0;
}