Cod sursa(job #1774330)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 8 octombrie 2016 20:08:54
Problema Cadrane Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

ifstream in ( "cadrane.in"  );
ofstream out( "cadrane.out" );

const int DIM = 1e5 + 5;
const int INF = 0x3f3f3f3f;

pair<int, int> p[DIM];
int segt[DIM * 8], lazy[DIM * 8];

bool cmp( pair<int, int> p1, pair<int, int> p2 ) {
    return p1.second < p2.second;
}

void update_l( int n, int l, int r ) {
    segt[n] += lazy[n];

    if( l != r ) {
        lazy[n * 2] += lazy[n];
        lazy[n * 2 + 1] += lazy[n];
    }

    lazy[n] = 0;
    return;
}

void build( int n, int l, int r ) {
    if( l > r ) {
        segt[n] = INT_MAX;
        return;
    }

    segt[n] = 0;

    if( l == r )
        return;

    int m = l + (r - l) / 2;

    build( n * 2, l, m );
    build( n * 2 + 1, m + 1, r );

    return;
}

void update( int n, int l, int r, int st, int fi, int x ) {
    if( lazy[n] != 0 )
        update_l( n, l, r );

    if( l > r || l > fi || r < st )
        return;

    if( st <= l && r <= fi ) {
        lazy[n] += x;
        update_l( n, l, r );
        return;
    }

    int m = l + (r - l) / 2;

    update( n * 2, l, m, st, fi, x );
    update( n * 2 + 1, m + 1, r, st, fi, x );

    segt[n] = min( segt[n * 2], segt[n * 2 + 1] );
    return;
}

int query( int n, int l, int r, int st, int fi ) {
    if( lazy[n] != 0 )
        update_l( n, l, r );

    if( l > r || l > fi || r < st )
        return INT_MAX;

    if( st <= l && r <= fi )
        return segt[n];

    int m = l + (r - l) / 2;

    int ans1 = query( n * 2, l, m, st, fi );
    int ans2 = query( n * 2 + 1, m + 1, r, st, fi );

    return min( ans1, ans2 );
}

int main( int argc, const char *argv[] ) {

    int n, m, ans = 0; in >> n;

    for( int i = 0; i < n; i ++ )
        in >> p[i].first >> p[i].second;

    sort( p + 1, p + n + 1, cmp );

    for( int i = 1, j = 1, k = 1; i <= n; i = j + 1, j = i, m = k, k ++ ) {
        while( j < n && p[i].second == p[j + 1].second )
            j ++;

        for( int l = i; l <= j; l ++ )
            p[l].second = k;
    }

    sort( p + 1, p + n + 1 );
    build( 1, 1, 2 * m );

    for( int i = 1; i <= n; i ++ )
        update( 1, 1, 2 * m, p[i].second, p[i].second + m, 1 );

    for( int i = 1, j = 1; i <= n; i = j ) {
        while( j <= n && p[i].first == p[j].first ) {
            update( 1, 1, 2 * m, p[j].second + m, 2 * m, +1 );
            update( 1, 1, 2 * m, p[j].second, p[j].second + m, -1 );
            j ++;
        }

        ans = max( ans, query( 1, 1, 2 * m, m, 2 * m ) );
    }

    out << ans << endl;
    return 0;
}