Cod sursa(job #993196)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 3 septembrie 2013 14:41:04
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 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';
}