oj.uz

Submission #883046

# Submission time Handle Problem Language Result Execution time Memory
883046 2023-12-04T12:43:51 Z LucaIlie Team Contest (JOI22_team) C++17
0 / 100
 2000 ms 15828 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 2e5;
const int INF = 1e8;
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 == 0 ? -INF : ans);
    }
} aib;

struct AIB2d {
    AIB aib[MAX_N + 1];

    void init() {
        for ( int i = 0; i <= MAX_N; 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 == 0 ? -INF : 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;

map<int, int> normA, normB, normC;

int main() {
    int n;

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

    for ( int i = 0; i < n; i++ ) {
        normA[v[i].a] = 1;
        normB[v[i].b] = 1;
        normC[v[i].c] = 1;
    }

    int x;
    x = 0;
    for ( auto p: normA )
        normA[p.first] = ++x;
    x = 0;
    for ( auto p: normB )
        normB[p.first] = ++x;
    x = 0;
    for ( auto p: normC )
        normC[p.first] = ++x;

    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 = -1;
    int l = 0, r = 0;
    aib2d.init();
    while ( l < n ) {
        r = l;
        while ( r < n && 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 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14968 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 5 ms 14940 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 4 ms 14940 KB Output is correct
12 Correct 5 ms 14976 KB Output is correct
13 Correct 4 ms 14936 KB Output is correct
14 Execution timed out 2091 ms 14972 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14968 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 5 ms 14940 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 4 ms 14940 KB Output is correct
12 Correct 5 ms 14976 KB Output is correct
13 Correct 4 ms 14936 KB Output is correct
14 Execution timed out 2091 ms 14972 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14936 KB Output is correct
5 Correct 4 ms 14948 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 263 ms 15828 KB Output is correct
12 Incorrect 168 ms 15536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14936 KB Output is correct
5 Correct 4 ms 14948 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 263 ms 15828 KB Output is correct
12 Incorrect 168 ms 15536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14936 KB Output is correct
5 Correct 4 ms 14948 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 263 ms 15828 KB Output is correct
12 Incorrect 168 ms 15536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14936 KB Output is correct
5 Correct 4 ms 14948 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 263 ms 15828 KB Output is correct
12 Incorrect 168 ms 15536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14968 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 4 ms 14940 KB Output is correct
9 Correct 5 ms 14940 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 4 ms 14940 KB Output is correct
12 Correct 5 ms 14976 KB Output is correct
13 Correct 4 ms 14936 KB Output is correct
14 Execution timed out 2091 ms 14972 KB Time limit exceeded
15 Halted 0 ms 0 KB -