Cod sursa(job #1506437)

Utilizator tudormaximTudor Maxim tudormaxim Data 20 octombrie 2015 17:54:05
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 100005;
pair <int,int> v[nmax], arb[nmax<<2];
int n, m, sol, x[nmax];

void update (int nod,int st,int dr,int poz,int val)
{
    if (st==dr)
    {
        arb[nod].first+=val;
        arb[nod].second=arb[nod].first;
        return;
    }
    int mij=(st+dr)/2;
    if (poz<=mij) update(nod<<1, st, mij, poz, val);
    else update((nod<<1)|1, mij+1, dr, poz, val);
    arb[nod].first=arb[nod<<1].first+arb[(nod<<1)|1].first;
    arb[nod].second=min(arb[nod<<1].second, arb[nod<<1].first+arb[(nod<<1)|1].second);
}

int main ()
{
    freopen ("cadrane.in", "r", stdin);
    freopen ("cadrane.out", "w", stdout);
    int i, j, k, nrc;
    scanf ("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d%d", &v[i].first, &v[i].second);
        x[++m]=v[i].second;
    }
    sort(v+1, v+n+1);
    sort(x+1, x+m+1);

    for(i=1, j=2; j<=m; j++)
        if (x[i]!=x[j]) x[++i]=x[j];
    m=i;
    for(i=1; i<=n; i++)
    {
        v[i].second=lower_bound (x+1, x+m+1, v[i].second)-x;
        update(1, 1, n, v[i].second+1, -1);
    }

    nrc=n;
    for(i=j=1; i<=n; i=j)
    {
        while(j<=n && v[i].first==v[j].first)
            update(1, 1, n, v[j++].second+1, 1);
        sol=max(sol, nrc+arb[1].second);
        nrc-=j-i;
        for(k=i; k<j; k++)
            update (1, 1, n, v[k].second, 1);
    }
    printf ("%d", sol);
    fclose(stdin);
    fclose(stdout);
    return 0;
}