oj.uz

Submission #883030

# Submission time Handle Problem Language Result Execution time Memory
883030 2023-12-04T12:32:01 Z LucaIlie Team Contest (JOI22_team) C++17
0 / 100
 13 ms 21596 KB 
#include <bits/stdc++.h>

using namespace std;

struct abc {
    int a, b, c;
};

const int MAX_N = 1.5e5;
int bestB[MAX_N], bestC[MAX_N];
abc v[MAX_N];

struct AIB {
    unordered_map<int, int> aib;

    void init() {
        aib.clear();
    }

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

    int query( int i ) {
        int ans = 0;
        while ( i > 0 ) {
            ans = max( ans, aib[i] );
            i -= (i & -i);
        }
        return ans;
    }
} aib;

struct AIB2d {
    AIB aib[MAX_N + 1];

    void init() {
        for ( int i = 0; i <= MAX_N + 1; i++ )
            aib[i].aib.clear();
    }

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

    int query( int i, int j ) {
        int ans = 0;
        while ( i > 0 ) {
            ans = max( ans, aib[i].query( j ) );
            i -= (i & -i);
        }
        return ans;
    }

    void updateInv( int i, int j, int x ) {
        update( MAX_N + 1 - i, MAX_N + 1 - j, x );
    }

    int queryInv( int i, int j ) {
        return query( MAX_N + 1 - i, MAX_N + 1 - j );
    }
} aib2d;


int main() {
    int n;

    cin >> n;
    for ( int i = 0; i < n; i++ )
        cin >> v[i].a >> v[i].b >> v[i].c;

    sort( v, v + n, []( abc a, abc b ) {
        return a.a < b.a;
    } );

    aib.init();
    for ( int i = 0; i < n; i++ ) {
        bestC[i] = aib.query( v[i].b - 1 );
        aib.update( v[i].b, v[i].c );
    }
    aib.init();
    for ( int i = 0; i < n; i++ ) {
        bestB[i] = aib.query( v[i].c - 1 );
        aib.update( v[i].c, v[i].b );
    }

    int ans = 0;
    int l = 0, r = 0;
    aib2d.init();
    while ( l < n ) {
        r = l;
        while ( v[l].a == v[r].a )
            r++;
        for ( int i = l; i < r; i++ )
            ans = max( ans, v[i].a + aib2d.queryInv( v[i].b + 1, v[i].c + 1 ) );
        for ( int i = l; i < r; i++ ) {
            aib2d.updateInv( v[i].b, bestC[i], v[i].b + bestC[i] );
            aib2d.updateInv( bestB[i], v[i].c, bestB[i] + v[i].c );
        }
        l = r;
    }

    cout << ans;

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 21592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 21592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 21596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 21592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -