Cod sursa(job #1813164)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 22 noiembrie 2016 19:15:57
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>

#define pii pair <int, int>
#define f first
#define s second

using namespace std;

queue <int> q;
map <int, int> mpx, mpy;
int arb[250000], lazy[150000], n;
pii v[100010];
vector <int> xx, yy;

inline void propag (int nod, int st, int dr)
{
    if (st == dr || !lazy[nod]) return;
    int mij = (st + dr) >> 1;
    arb[nod] += lazy[nod];

    if (st == mij) arb[nod << 1] += lazy[nod];
    else lazy[nod << 1] += lazy[nod];

    if (mij + 1 == dr) arb[nod << 1 | 1] += lazy[nod];
    else lazy[nod << 1 | 1] += lazy[nod];

    lazy[nod] = 0;
}

inline void update (int st, int dr, int a, int b, int nod, int val)
{
    if (a > b) return;

    propag (nod, st, dr);
    if (a <= st && dr <= b)
    {
        if (st == dr) arb[nod] += val;
        else lazy[nod] += val, propag (nod, st, dr);

        return;
    }

    int mij = (st + dr) >> 1;
    if (a <= mij) update (st, mij, a, b, nod << 1, val);
    else propag (nod << 1, st, mij);

    if (b > mij) update (mij + 1, dr, a, b, nod << 1 | 1, val);
    else propag (nod << 1 | 1, mij + 1, dr);

    arb[nod] = min (arb[nod << 1], arb[nod << 1 | 1]);
}

int main ()
{
    freopen ("cadrane.in", "r", stdin);
    freopen ("cadrane.out", "w", stdout);

    scanf ("%d", &n);

    for (int i = 1; i <= n; ++i)
        scanf ("%d %d", &v[i].f, &v[i].s),
        xx.push_back (v[i].f),
        yy.push_back (v[i].s);

    sort (xx.begin (), xx.end ());
    sort (yy.begin (), yy.end ());

    int k = 1, p = 1;
    for (int i = 0; i < n; ++i)
    {
        if (i > 1) if (xx[i] != xx[i - 1]) ++k;
        if (i > 1) if (yy[i] != yy[i - 1]) ++p;

        mpx[xx[i]] = k;
        mpy[yy[i]] = p;
    }

    for (int i = 1; i <= n; ++i)
        v[i].f = mpx[v[i].f],
        v[i].s = mpy[v[i].s];

    sort (v + 1, v + n + 1);

    for (int i = 1; i <= n; ++i)
        update (1, p, 1, v[i].s, 1, 1);

    propag (1, 1, p);
    int ma = arb[1];
    for (int i = 1; i <= n + 1; ++i)
    {
        if (i > 1 && v[i].f != v[i - 1].f)
        {
            propag (1, 1, p);
            ma = max (ma, arb[1]);

            for (; !q.empty (); q.pop ())
                update (1, p, 1, q.front () - 1, 1, -1);
        }

        update (1, p, v[i].s + 1, p, 1, 1);
        q.push (v[i].s);
    }

    printf ("%d\n", ma);

    return 0;
}