Cod sursa(job #2785684)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 19 octombrie 2021 11:08:54
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#include <algorithm>

#define MAX_N 100000

using std::sort;

struct oaie {
    int timp, lana;
    bool operator < (const oaie &b ) const {
        if ( lana == b.lana )
            return timp > b.timp;
        return lana > b.lana;
    }
};

int aib[MAX_N + 1];
oaie v[MAX_N];

int query( int i ) {
    int x;

    x = 0;
    while ( i > 0 ) {
        x += aib[i];
        i -= (i & -i);
    }

    return x;
}

void update( int i, int x, int n ) {
    while ( i <= n ) {
        aib[i] += x;
        i += (i & -i);

    }
}

int main() {
    FILE *fin, *fout;
    int n, d, l, dist, st, dr, mij, i;
    long long sumaLana;

    fin = fopen( "lupu.in", "r" );
    fscanf( fin, "%d%d%d", &n, &d, &l );
    for ( i = 0; i < n; i++ ) {
        fscanf( fin, "%d%d", &dist, &v[i].lana );
        v[i].timp = (d - dist) / l + 1;
        v[i].timp = v[i].timp < n ? v[i].timp : n;
    }
    fclose( fin );

    sort( v, v + n );

    sumaLana = 0;
    for ( i = 0; i < n; i++ ) {
        if ( v[i].timp >= 1 ) {
            st = 0;
            dr = v[i].timp;
            while ( dr - st > 1 ) {
                mij = (st + dr) / 2;
                if ( query( v[i].timp ) - query( mij ) < v[i].timp - mij  )
                    st = mij;
                else
                    dr = mij;
            }
            if ( query( dr ) == query( st ) ) {
                sumaLana += v[i].lana;
                update( dr, 1, n );
            }
        }
    }

    fout = fopen( "lupu.out", "w" );
    fprintf( fout, "%lld", sumaLana );
    fclose( fout );

    return 0;
}