Cod sursa(job #3364354)

Utilizator iustincmbMaican Iustin iustincmb Data 2 septembrie 2026 08:10:13
Problema Cadrane Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <bits/stdc++.h>
using namespace std;
#define int long long


map<int, int>M;
int val[200005];

int x[100005];
int b[100005];
int a[100005];

struct node
{
    int sum, pref_sum;
}aint[400005];

void join(int node, int st, int dr)
{
    if(st!=dr)
    {
        aint[node].sum=aint[2*node].sum+aint[2*node+1].sum;
        aint[node].pref_sum=min(aint[2*node].pref_sum, 
            aint[2*node].sum+aint[2*node+1].pref_sum);
    }
}
void init(int node, int st, int dr)
{
    if(st==dr)
        aint[node].sum=x[st], aint[node].pref_sum=min(x[st], 0LL);
    else
    {
        int mid=(st+dr)/2;
        init(2*node, st, mid);
        init(2*node+1, mid+1, dr);
        join(node, st, dr);
    }
}
void update(int node, int st, int dr, int poz, int val)
{
    if(st==dr)
        aint[node].sum+=val, aint[node].pref_sum=min(0LL, aint[node].sum);
    
    else
    {
        int mid=(st+dr)/2;
        
        if(poz<=mid)
            update(2*node, st, mid, poz, val);
        else
            update(2*node+1, mid+1, dr, poz, val);
        join(node, st, dr);
    }
}

struct point
{
    int x, y;
}v[100005];

int f[200005];
int line[200005];
int col[200005];
vector<int> on_line[200005];
vector<int> on_col[200005];
int32_t main()
{
    ifstream cin ("cadrane.in");
    ofstream cout ("cadrane.out");
    int n, l=0;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> v[i].x >> v[i].y;
        swap(v[i].x, v[i].y);
        val[++l]=v[i].x, val[++l]=v[i].y;
    }
    sort(val+1, val+l+1);
    int cnt=1;
    for(int i=1; i<=l; i++)
    {
        if(val[i]!=val[i-1] && i>1)
            cnt++;
        M[val[i]]=cnt;
    }
    
    for(int i=1; i<=n; i++)
        v[i].x=M[v[i].x], v[i].y=M[v[i].y];
    
    for(int i=1; i<=n; i++)
        line[i]=v[i].y, col[i]=v[i].x;

    sort(line+1, line+n+1);
    sort(col+1, col+n+1);
    
    cnt=1;
    for(int i=1; i<=n; i++)
    {
        if(col[i]!=col[i-1] && i>1)
            cnt++;
        f[col[i]]=cnt;
    }
    
    for(int i=1; i<=n; i++)
        on_col[f[v[i].x]].push_back(v[i].y);
    
    for(int i=1; i<=n; i++)
        on_line[v[i].y].push_back(f[v[i].x]);
    // f[col[i]] da encrypt la coloana
    // cnt e nr de coloane
    // on_line spune ce coloane sunt pe linia j
    
    int S=0;
    
    for(int i=1; i<=cnt; i++)
    {
        a[i]=0;
        b[i]=on_col[i].size();
        S+=b[i];
    }
    for(int i=1; i<=cnt-1; i++)
        x[i]=a[i+1]-b[i];
    if(cnt>1)
    {
        init(1, 1, cnt-1);
        int rasf=-1e18;
        int cnt1=0;
        for(int i=1; i<=n; i++)
        {
            if(i==1 || line[i]!=line[i-1])
            {
                for(auto j : on_line[line[i]])
                {
                    b[j]--;
                    if(j<cnt)
                        update(1, 1, cnt-1, j, 1);
                }
                rasf=max(rasf, S+aint[1].pref_sum);
                for(auto j : on_line[line[i]])
                {
                    a[j]++, S--;
                    if(j>1)
                        update(1, 1, cnt-1, j-1, 1);
                }
            }
        }
        cout << rasf;
    }
    else
        cout << n;
    return 0;
}