Cod sursa(job #2508927)

Utilizator borcanirobertBorcani Robert borcanirobert Data 13 decembrie 2019 14:55:19
Problema Cadrane Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

using VI  = std::vector<int>;
using VVI = std::vector<VI>;
using VB  = std::vector<bool>;

struct Point{
    Point() : x{0}, y{0}
    {}

    Point(int x, int y) : x{x}, y{y}
    {}

    int x, y;

    bool operator < (const Point& p) const
    {
        return x < p.x || (x == p.x && y < p.y);
    }
};

class SegmTree{
public:
    SegmTree(int x, int y)
        : x{x}, y{y}, val{0}, lazy{0},
          left{nullptr}, right{nullptr}
    {
        if (x != y)
        {
            int mid = (x + y) / 2;
            left = new SegmTree(x, mid);
            right = new SegmTree(mid + 1, y);
        }
    }

    void Update(int begin, int end, int val)
    {
        Propagate();

        if (end < x || begin > y)
            return;

        if (begin <= x && y <= end)
        {
            lazy = val;
            Propagate();

            return;
        }

        left->Update(begin, end, val);
        right->Update(begin, end, val);

        this->val = std::min(left->val, right->val);
    }

    int GetMinimum()
    {
        Propagate();

        return val;
    }

    ~SegmTree()
    {
        delete left;
        delete right;
    }

private:
    void Propagate()
    {
        val += lazy;

        if (x != y)
        {
            left->lazy += lazy;
            right->lazy += lazy;
        }

        lazy = 0;
    }

    int x, y;
    int val;
    int lazy;
    SegmTree *left, *right;
};

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

int N;
std::vector<Point> p, a;
VI cx, cy;

void ReadData();
void Solve();
void NormalizePoints();
void WritePoints(const std::vector<Point>& p);

int main()
{
    ReadData();
    Solve();

    fin.close();
    fout.close();
    return 0;
}

void ReadData()
{
    fin >> N;

    p = std::vector<Point>(N);
    for (int i = 0; i < N; ++i)
        fin >> p[i].x >> p[i].y;
}

void Solve()
{
    NormalizePoints();
    std::sort(a.begin(), a.end());

    int cnt_px0{0};
    SegmTree st(0, cy.size() - 1);
    for (const Point& p : a)
    {
        if (p.x == 0)
        {
            ++cnt_px0;
            continue;
        }

        st.Update(0, p.y, +1);
    }

    int ymax = static_cast<int>(cy.size() - 1);
    int res = cnt_px0 + st.GetMinimum();

    int i{0};
    while (i < N && a[i].x == a[0].x)
        ++i;

    for (; i < N; ++i)
    {
        int j{i - 1};
        while (j >= 0 && a[j].x == a[i - 1].x)
        {
            st.Update(a[j].y, ymax, +1);
            --j;
        }

        int cnt{1};
        st.Update(0, a[i].y, -1);

        while (i + 1 < N && a[i + 1].x == a[i].x)
        {
            ++i; ++cnt;
            st.Update(0, a[i].y, -1);
        }

        res = std::max(res, st.GetMinimum() + cnt);
    }

    fout << res << '\n';
}

void NormalizePoints()
{
    for (const Point& pt : p)
    {
        cx.emplace_back(pt.x);
        cy.emplace_back(pt.y);
    }

    std::sort(cx.begin(), cx.end());
    std::sort(cy.begin(), cy.end());
    cx.erase(unique(cx.begin(), cx.end()), cx.end());
    cy.erase(unique(cy.begin(), cy.end()), cy.end());

    for (const Point& pt : p)
    {
        int x = std::find(cx.begin(), cx.end(), pt.x) - cx.begin();
        int y = std::find(cy.begin(), cy.end(), pt.y) - cy.begin();

        a.emplace_back(x, y);
    }

    //WritePoints(a);
}

void WritePoints(const std::vector<Point>& p)
{
    for (const Point& pt : p)
    {
        std::cout << pt.x << ' ' << pt.y << '\n';
    }
}