Cod sursa(job #2878803)

Utilizator puica2018Puica Andrei puica2018 Data 27 martie 2022 19:35:21
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 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());
    vector<pair<int,int>> nc(N);
    int X = 1;
    nc[xs[0].second].first = 1;
    for (int i = 1; i < N; ++i)
    {
        if (xs[i].first != xs[i - 1].first)
            ++X;
        nc[xs[i].second].first = X;
    }
    int Y = 1;
    nc[ys[0].second].second = 1;
    for (int i = 1; i < N; ++i) {
        if (ys[i].first != ys[i - 1].first)
            ++Y;
        nc[ys[i].second].second = Y;
    }
    vector<int> adj[X + 1];
    SegTree tree(Y);
    for (auto p : nc) {
        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;
}