Cod sursa(job #1959736)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 9 aprilie 2017 20:46:25
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("cadrane.in");
ofstream g("cadrane.out");
int i,n,m,sol,j,nmax,P[100005];
struct nod
{
    int val,lazy;
}A[1<<19];
struct pt
{
    int x,y,ind;
}v[1<<17];
bool cmp (pt a,pt b) { return a.y<b.y; }
bool cmp_(pt a,pt b) { return a.x<b.x; }
void update(int nod,int l,int r,int st,int dr,int value)
{
    if(st<=l&&r<=dr)
    {
        A[nod].lazy+=value;
        return;
    }
    int m=(l+r)>>1;
    int left=nod<<1;
    int right=left+1;
    if(A[nod].lazy!=0)
    {
        update(left,l,m,l,m,A[nod].lazy);
        update(right,m+1,r,m+1,r,A[nod].lazy);
        A[nod].lazy=0;
    }
    if(st<=m) update(left,l,m,st,dr,value);
    if(m<dr) update(right,m+1,r,st,dr,value);
    A[nod].val=min(A[left].val+A[left].lazy,A[right].val+A[right].lazy);
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>v[i].x>>v[i].y;
        v[i].ind=i;
    }
    sort(v+1,v+n+1,cmp);
    P[v[1].ind]=1;
    for(i=2;i<=n;++i)
    {
        P[v[i].ind]=P[v[i-1].ind];
        if(v[i].y!=v[i-1].y) P[v[i].ind]++;
    }
    nmax=P[v[n].ind];
    sort(v+1,v+n+1,cmp_);
    for(i=1;i<=n;i++) update(1,1,nmax,1,P[v[i].ind],1);
    for(i=j=1;i<=n;++i)
    {
        update(1,1,nmax,P[v[i].ind],nmax,1);
        if(v[i].x!=v[i+1].x)
        {
            sol=max(sol,A[1].val+A[1].lazy);
            while(j<=i) update(1,1,nmax,1,P[v[j].ind],-1),j++;
        }
    }
    g<<sol;
    return 0;
}