Cod sursa(job #2877006)

Utilizator Tudor06MusatTudor Tudor06 Data 24 martie 2022 02:01:22
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;

struct point {
    int x;
    int y;
} v[NMAX];
bool cmp( point a, point b ) {
    return a.x < b.x;
}
int normalizare( int n ) {
    map <int, int> cod;
    for ( int i = 0; i < n; i ++ )
        cod[v[i].y] = 1;
    int j = cod.size() - 1;

    for ( auto& i : cod )
        i.second = j--;
    for ( int i = 0; i < n; i ++ )
        v[i].y = cod[v[i].y];
    return cod.size() - 1;
}
struct node {
    int minim;
    int lazy;
} aint[8 * NMAX];

void propag( int i ) {
    if ( aint[i].lazy == 0 ) return;
    int& l = aint[i].lazy;
    aint[i * 2 + 1].minim += l;
    aint[i * 2 + 1].lazy += l;
    aint[i * 2 + 2].minim += l;
    aint[i * 2 + 2].lazy += l;
    l = 0;
}

void update( int st, int dr, int a, int b, int i, int add ) {
    if ( a > b ) return;
    propag( i );
    if ( st == a && b == dr ) {
        aint[i].minim += add;
        aint[i].lazy += add;
        return;
    }
    int mij = ( st + dr ) / 2;
    if ( b <= mij )
        update( st, mij, a, b, i * 2 + 1, add );
    else if ( a > mij )
        update( mij + 1, dr, a, b, i * 2 + 2, add );
    else {
        update( st, mij, a, mij, i * 2 + 1, add );
        update( mij + 1, dr, mij + 1, b, i * 2 + 2, add );
    }
    aint[i].minim = min( aint[i * 2 + 1].minim, aint[i * 2 + 2].minim );
}

int main() {
    ifstream fin( "cadrane.in" );
    ofstream fout( "cadrane.out" );
    int n, i, x, y, m;
    fin >> n;
    for ( i = 0; i < n; i ++ )
        fin >> v[i].x >> v[i].y;
    m = normalizare( n );
    sort( v, v + n, cmp );
    for ( i = 0; i < n; i ++ )
        update( 0, m, v[i].y, m, 0, 1 );
    int ans = i = 0;
    while ( i < n ) {
        int x = v[i].x, j = i;
        while ( j < n && v[j].x == x ) {
            update( 0, m, 0, v[j].y - 1, 0, 1 );
            j ++;
        }
        ans = max( ans, aint[0].minim );
        while ( i < n && v[i].x == x ) {
            update( 0, m, v[i].y + 1, m, 0, -1 );
            i ++;
        }
    }
    fout << ans;

    return 0;
}