Cod sursa(job #1774384)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 8 octombrie 2016 21:14:36
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 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 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 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 );

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

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

        if( p[i].first != p[i + 1].first ) {
            ans = max( ans, segt[1] + lazy[1] );

            for( j = j; j <= i; j ++ )
                update( 1, 1, m, 1, p[j].second, -1 );
        }
    }

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