Cod sursa(job #2728088)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 22 martie 2021 19:47:09
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 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);
  }
  /// normalizare
  sort(xs.begin(), xs.end()), sort(ys.begin(), ys.end());
  vector<pair<int,int>> norm_coord(N);
  int X = 1;
  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);
  /// initial zic ca orice punct "adauga" la NE pentru punctele cu x mai mic sau egal ca al lor,
  /// respectiv y mai mic sau egal ca al lor. Pot astfel sa ma folosesc doar de y
  /// si sa adaug pentru orice x, deoarece eu fac parcurgerea in ordinea crescatoare
  /// cu respect fata de x, deci pot sa elimin pe parcurs punctele care defapt trec
  /// la stanga liniei de baleiere
  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);
        /// elimin alea cu x mai mic adaugate mai sus ca nu mai sunt bune(vreau
        /// sa am la NE x mai mare sau egal decat x-ul actual.
        /// Y-ul e ok pentru ca am restrictionat intervalul de update de mai sus
        /// la maxim y-ul punctului care ar trebui "sa adauge" la NE
    for (int y : adj[i])
      tree.update(1, 1, Y, y, Y, 1);
    /// punctele din viitor cu y mai mare sau egal ca y-ul punctului la care ma aflu acum
    /// vor avea din sortare sigur si x mai mare sau egal, deci punctul la care sunt acum
    /// "adauga" la SV pentru acele puncte
    max_self(ans, tree.tree[1]);
  }
  fout << ans << '\n';
  return 0;
}