Submission #502835

#	Time	Username	Problem	Language	Result	Execution time	Memory
502835		LucaIlie	Divide and conquer (IZhO14_divide)	C++17	48 / 100	152 ms	8488 KiB

divide

#include <iostream>
#include <algorithm>

#define MAX_N 100000
#define MAX_G 100000000000000

using namespace std;

struct val_and_poz {
    int poz;
    long long val;

    bool operator < (const val_and_poz &a) const {
        return val < a.val;
    }
};

struct AIB {
    long long aib[2 * MAX_N + 1];

    void init() {
        int i;

        for ( i = 0; i <= 2 * MAX_N; i++ )
            aib[i] = MAX_G + 1;
    }

    long long query( int i ) {
        long long minG;

        minG = MAX_G + 1;
        while ( i > 0 ) {
            minG = min( minG, aib[i] );
            i -= (i & -i);
        }

        return minG;
    }

    void update( int i, long long x ) {
        while ( i <= MAX_N ) {
            aib[i] = min( aib[i], x );
            i += (i & -i);
        }
    }
};

int x[MAX_N + 1], g[MAX_N + 1], d[MAX_N + 1], small[MAX_N + 1], big[MAX_N + 1];
long long sg[MAX_N + 1], sd[MAX_N + 1];
val_and_poz norm[2 * MAX_N];
AIB gold;

signed main() {
    int n, a, i;
    long long maxG;

    cin >> n;
    for ( i = 1; i <= n; i++ )
        cin >> x[i] >> g[i] >> d[i];

    for ( i = 1; i <= n; i++ ) {
        sg[i] = sg[i - 1] + g[i];
        sd[i] = sd[i - 1] + d[i];
    }

    for ( i = 0; i < n; i++ )
        norm[i] = { i, sd[i] - x[i + 1] };
    for ( i = 0; i < n; i++ )
        norm[n + i] = { n + i, sd[i + 1] - x[i + 1] };

    sort( norm, norm + 2 * n );

    a = 1;
    for ( i = 0; i < 2 * n; i++ ) {
        if ( norm[i].poz < n )
            small[norm[i].poz + 1] = a;
        else
            big[norm[i].poz - n + 1] = a;
        if ( i < 2 * n - 1 && norm[i].val != norm[i + 1].val )
            a++;
    }

    maxG = 0;
    gold.init();
    for ( i = 1; i <= n; i++ ) {
        gold.update( small[i], sg[i - 1] );
        maxG = max( maxG, sg[i] - gold.query( big[i] ) );
    }

    cout << maxG;

    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 0 / 52