oj.uz

Submission #883104

# Submission time Handle Problem Language Result Execution time Memory
883104 2023-12-04T14:34:59 Z LucaIlie Team Contest (JOI22_team) C++17
0 / 100
 407 ms 15960 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 2e5;
const int INF = 1e8;
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 {
    unordered_map<int, int> aib[MAX_N + 1];

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

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

    int query( int i, int j ) {
        int ans = 0;
        while ( i > 0 ) {
            int p = j;
            while ( p > 0 ) {
                ans = max( ans, aib[i][p] );
                p += (p & -p);
            }
            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() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );

    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 ) {
        if ( a.a == b.a )
            return a.b < b.b;
        return a.a < b.a;
    } );
    aib.init();
    for ( int i = 0; i < n; i++ ) {
        v[i].bestC = aib.query( normB[v[i].b] - 1 );
        aib.update( normB[v[i].b], v[i].c );
    }
    sort( v, v + n, []( abc a, abc b ) {
        if ( a.a == b.a )
            return a.c < b.c;
        return a.a < b.a;
    } );
    aib.init();
    for ( int i = 0; i < n; i++ ) {
        v[i].bestB = aib.query( normC[v[i].c] - 1 );
        aib.update( normC[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( normB[v[i].b] + 1, normC[v[i].c] + 1 ) );
        for ( int i = l; i < r; i++ ) {
            if ( v[i].bestC > v[i].c )
                aib2d.updateInv( normB[v[i].b], normC[v[i].bestC], v[i].b + v[i].bestC );
            if ( v[i].bestB > v[i].b )
                aib2d.updateInv( normB[v[i].bestB], normC[v[i].c], v[i].bestB + v[i].c );
        }
        l = r;
    }

    cout << ans;

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB Output is correct
2 Correct 4 ms 12888 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 5 ms 12940 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 4 ms 12888 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 5 ms 12888 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 6 ms 13400 KB Output is correct
15 Incorrect 6 ms 13148 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB Output is correct
2 Correct 4 ms 12888 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 5 ms 12940 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 4 ms 12888 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 5 ms 12888 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 6 ms 13400 KB Output is correct
15 Incorrect 6 ms 13148 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12892 KB Output is correct
2 Correct 4 ms 12948 KB Output is correct
3 Correct 4 ms 12940 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12940 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 407 ms 15960 KB Output is correct
12 Incorrect 263 ms 15492 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12892 KB Output is correct
2 Correct 4 ms 12948 KB Output is correct
3 Correct 4 ms 12940 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12940 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 407 ms 15960 KB Output is correct
12 Incorrect 263 ms 15492 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12892 KB Output is correct
2 Correct 4 ms 12948 KB Output is correct
3 Correct 4 ms 12940 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12940 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 407 ms 15960 KB Output is correct
12 Incorrect 263 ms 15492 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12892 KB Output is correct
2 Correct 4 ms 12948 KB Output is correct
3 Correct 4 ms 12940 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12940 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 407 ms 15960 KB Output is correct
12 Incorrect 263 ms 15492 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 12888 KB Output is correct
2 Correct 4 ms 12888 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 5 ms 12940 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 4 ms 12888 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 5 ms 12888 KB Output is correct
13 Correct 4 ms 12892 KB Output is correct
14 Correct 6 ms 13400 KB Output is correct
15 Incorrect 6 ms 13148 KB Output isn't correct
16 Halted 0 ms 0 KB -