Cod sursa(job #3317540)

Utilizator tudor_costinCostin Tudor tudor_costin Data 24 octombrie 2025 14:04:53
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cadrane.in");
ofstream fout("cadrane.out");
const int Nmax=1e5+5;
map<int,vector<int>> ev;
map<int,int> nrm;
int a[Nmax],b[Nmax];
int aint[4*Nmax],suma[4*Nmax],sumb[4*Nmax];
void build(int nod,int l,int r)
{
    if(l==r)
    {
        aint[nod]=a[l]+b[l];
        suma[nod]=a[l];
        sumb[nod]=b[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*nod,l,mid);
    build(2*nod+1,mid+1,r);
    suma[nod]=suma[2*nod]+suma[2*nod+1];
    sumb[nod]=sumb[2*nod]+sumb[2*nod+1];
    aint[nod]=min(sumb[2*nod]+aint[2*nod+1],aint[2*nod]+suma[2*nod+1]);
    return;
}
void update(int nod,int l,int r,int poz,int val,bool ina)
{
    if(l==r)
    {
        aint[nod]+=val;
        if(ina) suma[nod]+=val;
        else sumb[nod]+=val;
        return;
    }
    int mid=(l+r)/2;
    if(poz<=mid) update(2*nod,l,mid,poz,val,ina);
    else update(2*nod+1,mid+1,r,poz,val,ina);
    suma[nod]=suma[2*nod]+suma[2*nod+1];
    sumb[nod]=sumb[2*nod]+sumb[2*nod+1];
    aint[nod]=min(sumb[2*nod]+aint[2*nod+1],aint[2*nod]+suma[2*nod+1]);
}
int main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        fin>>x>>y;
        ev[x].push_back(y);
        nrm[y]++;
    }
    int cnt=1;
    for(auto [y,val]:nrm)
    {
        a[cnt]=val;
        nrm[y]=cnt;
        cnt++;
    }
    n=cnt-1;
    build(1,1,n);
    vector<int> cur;
    int ans=0;
    for(auto [x,nxt]:ev)
    {
        for(int y:cur) update(1,1,n,y,1,0);
        cur=nxt;
        int cnt=cur.size();
        for(int& y:cur)
        {
           /// cout<<x<<' '<<y<<' '<<nrm[y]<<'\n';
            y=nrm[y];
            update(1,1,n,y,-1,1);
        }
        ans=max(ans,cnt+aint[1]);
        ///cout<<ans<<'\n';
    }
    fout<<ans<<'\n';
    return 0;
}