Cod sursa(job #980037)

Utilizator danalex97Dan H Alexandru danalex97 Data 3 august 2013 19:26:37
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;

/**
*/

ifstream F("cadrane.in");
ofstream G("cadrane.out");

#define x first
#define y second
#define m_p make_pair
typedef pair<int,int> Pair;

const int Nmax = 100010;

int N,A[Nmax<<2],M[Nmax<<2];

Pair P[Nmax];
int poz[Nmax],S[Nmax];

bool cmp_y(int i,int j)
{
    return P[i].y < P[j].y;
}

void Norm_y()
{
    for (int i=1,now=1;i<=N;++i,++now)
    {
        for (;i+1<=N && P[poz[i]].y == P[poz[i+1]].y;++i)
            P[poz[i]].y = now;
        P[poz[i]].y = now;
    }
}

#define left (nod*2)
#define right (nod*2+1)

void Update(int nod,int st,int dr,int start,int stop,int val)
{
    if ( start <= st && dr <= stop  )
    {
        A[nod] += val*(dr-st+1);
        M[nod] += val;
        return;
    }

    int mid = ( st + dr ) / 2;

    if ( A[nod] != A[left] + A[right] )
    {
        int plus = (A[nod]-A[left]-A[right]) / (dr-st+1);
        A[left] += plus * (mid-st+1);
        A[right] += plus * (dr-mid);
        M[left] += plus , M[right] += plus;
    }

    if ( start <= mid ) Update(left,st,mid,start,stop,val);
    if ( stop > mid ) Update(right,mid+1,dr,start,stop,val);

    M[nod] = min( M[left],M[right] );
    A[nod] = A[left]+A[right];
}

void Add(int st,int dr,int val)
{
    Update(1,1,N,st,dr,val);
}

int main()
{
    F>>N;
    for (int i=1;i<=N;++i)
        F>>P[i].x>>P[i].y;
    sort(P+1,P+N+1);
    for (int i=1;i<=N;++i)
        poz[i] = i;
    sort(poz+1,poz+N+1,cmp_y);

    Norm_y();

    for (int i=1;i<=N;++i) ++S[P[i].y];
    for (int i=1;i<=N;++i) S[i] += S[i-1];
    for (int i=1;i<=N;++i) Add(i,i,N-S[i-1]);

    int now = 1,out = 0;
    for (int i=1;i<=N;++i)
    {
        for (;P[now].x < P[i].x;++now)
            Add(1,P[now].y,-1);
        for (;i+1<=N && P[i].x == P[i+1].x;++i)
            Add(P[i].y,N,1);
        Add(P[i].y,N,1);

        out = max(out,M[1]);
    }

    G<<out<<'\n';
}