oj.uz

Submission #502816

# Submission time Handle Problem Language Result Execution time Memory
502816 2022-01-06T15:38:13 Z LucaIlie Divide and conquer (IZhO14_divide) C++17
0 / 100
 1 ms 1100 KB 
#include <iostream>
#include <algorithm>

#define MAX_N 100000

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[MAX_N + 1];

    void init() {
        int i;

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

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

        minG = 2 * MAX_N + 2;
        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 + 2];
AIB gold;

int 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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1064 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1064 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Incorrect 1 ms 1088 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1064 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1064 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Incorrect 1 ms 1088 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1064 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1064 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Incorrect 1 ms 1088 KB Output isn't correct
7 Halted 0 ms 0 KB -