Cod sursa(job #2877003)

Utilizator Tudor06MusatTudor Tudor06 Data 24 martie 2022 01:03:52
Problema Cadrane Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 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 = 1;
    for ( auto& i : cod )
        i.second = j++;
    for ( int i = 0; i < n; i ++ )
        v[i].y = cod[v[i].y];
    return j;
}
struct node {
    int minim;
    int lazy;
} aint[4 * NMAX]; /// aint - numarul de y mai mari din stanga +
                    ///        numarul de y mai mici din dreapta

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 ) {
    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 query( int st, int dr, int a, int b, int i ) {
//    propag( i );
//    if ( st == a && dr == b ) {
//        return aint[i];
//    }
//    int mij = ( st + dr ) / 2;
//    if ( b <= mij ) return query( st, mij, a, b, i * 2 + 1 );
//    else if ( a > mij ) return query( mij + 1, dr, a, b, i * 2 + 2 );
//    else return min( query( st, mij, a, mij, i * 2 + 1 ),
//                     query( mij + 1, dr, mij + 1, b, i * 2 + 2 ) );
//}

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 = aint[0].minim;
    i = 0;
    while ( i < n ) {
        int x = v[i].x;
        while ( i < n && v[i].x == x ) {
            update( 0, m, 0, v[i].y, 0, 1 );
            update( 0, m, v[i].y, m, 0, -1 );
            i ++;
        }
        ans = max( ans, aint[0].minim );
    }
    fout << ans;

    return 0;
}