Cod sursa(job #2508724)

Utilizator ancabdBadiu Anca ancabd Data 12 decembrie 2019 20:54:25
Problema Cadrane Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin ("cadrane.in");
ofstream cout ("cadrane.out");

#define x first
#define y second

using VI = vector<int>;
using PI = pair<int, int>;
using PPI = pair<int, PI>;
using VPI = vector<PI>;
using VPPI = vector<PPI>;
using VVI = vector<VI>;

int n, ny, nx;
VPI coord;
VI arb, lazy;
VVI a;

bool compy(const PI& A, const PI& B)
{
    return A.y < B.y;
}

void normalizare();
void update(int, int, int, int, int, int);
void push(int, int, int);

int main()
{
    normalizare();

    arb = VI(4 * ny + 1);
    lazy = VI(4 * ny + 1);

    for (int i = 1; i <= n; ++ i)
        update(1, 1, ny, 1, coord[i].y, 1);

    int rez = 0;
    for (int i = 0; i < nx; ++ i)
    {
        for (int j = 0; j < a[i].size(); j ++)
            update(1, 1, ny, coord[i].y, ny, 1);
        if (i != 0)
            for (int j = 0; j < a[i - 1].size(); j ++)
                update(1, 1, ny, coord[i - 1].y, ny, -1);

        rez = max(arb[1], rez);
    }

    cout << rez;
    return 0;
}
void normalizare()
{
    cin >> n;
    coord = VPI(n + 1);
    for (int i = 1; i <= n; ++ i)
        cin >> coord[i].x >> coord[i].y;

    sort(coord.begin() + 1, coord.end(), compy);

    int aux = 0;
    for (int i = 1; i <= n; ++ i)
        if (coord[i].y != aux || i == 1)
        {
            aux = coord[i].y;
            coord[i].y = ++ ny;
        }
        else coord[i].y = ny;

    sort(coord.begin() + 1, coord.end());

    for (int i = 1; i <= n;)
    {
        a.push_back(VI());

        aux = coord[i].x;
        while (coord[i].x == aux)
        {
            a.back().push_back(coord[i].y);
            ++ i;
        }
    }

    nx = a.size();
}
void update(int node, int st, int dr, int L, int R, int val)
{
    if (L <= st && dr <= R)
    {
        arb[node] += val;
        lazy[node] += val;
        return;
    }

    if (lazy[node])push(node, st, dr);

    int mijl = (st + dr)/2;
    if (L <= mijl)update(2 * node, st, mijl, L, R, val);
    if (R > mijl)update(2 * node + 1, mijl + 1, dr, L, R, val);

    arb[node] = min(arb[2 * node], arb[2 * node + 1]);
}

void push(int node, int st, int dr)
{
    if (st == dr)
    {
        lazy[node] = 0;
        return;
    }

    lazy[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];

    arb[2 * node] += lazy[node];
    arb[2 * node + 1] += lazy[node];

    lazy[node] = 0;



}