Cod sursa(job #2877005)

Utilizator Tudor06MusatTudor Tudor06 Data 24 martie 2022 01:58:58
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.31 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 || ( a.x == b.x && a.y < b.y);
}
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]; /// 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;
    aint[i].lazy = 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 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 ) );
//}
void afis_aint( int st, int dr, int i ) {
    propag( i );
    if ( st == dr ) cout << aint[i].minim << ' ';
    else {
        int mij = ( st + dr ) / 2;
        afis_aint( st, mij, i * 2 + 1 );
        afis_aint( mij + 1, dr, 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 );
//    cout << m << endl;
    sort( v, v + n, cmp );
    for ( i = 0; i < n; i ++ ) {
//        cout << v[i].x << ' ' << v[i].y << endl;
        update( 0, m, v[i].y, m, 0, 1 );
    }
//    x = v[0].x;
//    i = 0;
//    while ( i < n && v[i].x == x ) {
//        update( 0, m, 0, v[i].y - 1, 0, 1 );
//        i ++;
//    }
//    afis_aint( 0, m, 0 );
//    cout << endl;
    i = 0;
    int ans = 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 ++;
        }
        j = i;
//        afis_aint( 0, m, 0 ); cout << endl;
        ans = max( ans, aint[0].minim );
        while ( j < n && v[j].x == x ) {
            update( 0, m, v[j].y + 1, m, 0, -1 );
            j ++;
        }
        i = j;
    }
    fout << ans;

    return 0;
}