Submission #883090

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
883090	2023-12-04T13:49:18 Z	LucaIlie	Team Contest (JOI22_team)	C++17	9 / 100	779 ms	25948 KB

team

#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 {
    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( 5 + 1 - i, 5 + 1 - j, x );
    }

    int queryInv( int i, int j ) {
        return query( 5 + 1 - i, 5 + 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 ) {
        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	12892 KB	Output is correct
3	Correct	4 ms	12892 KB	Output is correct
4	Correct	4 ms	12892 KB	Output is correct
5	Correct	4 ms	12892 KB	Output is correct
6	Correct	3 ms	12892 KB	Output is correct
7	Correct	4 ms	12892 KB	Output is correct
8	Correct	4 ms	13144 KB	Output is correct
9	Correct	4 ms	12888 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct
11	Correct	3 ms	12892 KB	Output is correct
12	Correct	4 ms	12892 KB	Output is correct
13	Correct	4 ms	12892 KB	Output is correct
14	Runtime error	13 ms	25948 KB	Execution killed with signal 11
15	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	12892 KB	Output is correct
3	Correct	4 ms	12892 KB	Output is correct
4	Correct	4 ms	12892 KB	Output is correct
5	Correct	4 ms	12892 KB	Output is correct
6	Correct	3 ms	12892 KB	Output is correct
7	Correct	4 ms	12892 KB	Output is correct
8	Correct	4 ms	13144 KB	Output is correct
9	Correct	4 ms	12888 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct
11	Correct	3 ms	12892 KB	Output is correct
12	Correct	4 ms	12892 KB	Output is correct
13	Correct	4 ms	12892 KB	Output is correct
14	Runtime error	13 ms	25948 KB	Execution killed with signal 11
15	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	13048 KB	Output is correct
2	Correct	4 ms	12892 KB	Output is correct
3	Correct	4 ms	12892 KB	Output is correct
4	Correct	4 ms	12892 KB	Output is correct
5	Correct	5 ms	12888 KB	Output is correct
6	Correct	4 ms	12892 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	779 ms	14960 KB	Output is correct
12	Correct	313 ms	14960 KB	Output is correct
13	Correct	141 ms	15580 KB	Output is correct
14	Correct	535 ms	15816 KB	Output is correct
15	Correct	361 ms	15840 KB	Output is correct
16	Correct	117 ms	15708 KB	Output is correct

Subtask #4
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	13048 KB	Output is correct
2	Correct	4 ms	12892 KB	Output is correct
3	Correct	4 ms	12892 KB	Output is correct
4	Correct	4 ms	12892 KB	Output is correct
5	Correct	5 ms	12888 KB	Output is correct
6	Correct	4 ms	12892 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	779 ms	14960 KB	Output is correct
12	Correct	313 ms	14960 KB	Output is correct
13	Correct	141 ms	15580 KB	Output is correct
14	Correct	535 ms	15816 KB	Output is correct
15	Correct	361 ms	15840 KB	Output is correct
16	Correct	117 ms	15708 KB	Output is correct
17	Correct	3 ms	12888 KB	Output is correct
18	Correct	3 ms	12888 KB	Output is correct
19	Correct	4 ms	12888 KB	Output is correct
20	Runtime error	14 ms	25724 KB	Execution killed with signal 11
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	13048 KB	Output is correct
2	Correct	4 ms	12892 KB	Output is correct
3	Correct	4 ms	12892 KB	Output is correct
4	Correct	4 ms	12892 KB	Output is correct
5	Correct	5 ms	12888 KB	Output is correct
6	Correct	4 ms	12892 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	779 ms	14960 KB	Output is correct
12	Correct	313 ms	14960 KB	Output is correct
13	Correct	141 ms	15580 KB	Output is correct
14	Correct	535 ms	15816 KB	Output is correct
15	Correct	361 ms	15840 KB	Output is correct
16	Correct	117 ms	15708 KB	Output is correct
17	Correct	3 ms	12888 KB	Output is correct
18	Correct	3 ms	12888 KB	Output is correct
19	Correct	4 ms	12888 KB	Output is correct
20	Runtime error	14 ms	25724 KB	Execution killed with signal 11
21	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	13048 KB	Output is correct
2	Correct	4 ms	12892 KB	Output is correct
3	Correct	4 ms	12892 KB	Output is correct
4	Correct	4 ms	12892 KB	Output is correct
5	Correct	5 ms	12888 KB	Output is correct
6	Correct	4 ms	12892 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	779 ms	14960 KB	Output is correct
12	Correct	313 ms	14960 KB	Output is correct
13	Correct	141 ms	15580 KB	Output is correct
14	Correct	535 ms	15816 KB	Output is correct
15	Correct	361 ms	15840 KB	Output is correct
16	Correct	117 ms	15708 KB	Output is correct
17	Correct	3 ms	12888 KB	Output is correct
18	Correct	3 ms	12888 KB	Output is correct
19	Correct	4 ms	12888 KB	Output is correct
20	Runtime error	14 ms	25724 KB	Execution killed with signal 11
21	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	12892 KB	Output is correct
3	Correct	4 ms	12892 KB	Output is correct
4	Correct	4 ms	12892 KB	Output is correct
5	Correct	4 ms	12892 KB	Output is correct
6	Correct	3 ms	12892 KB	Output is correct
7	Correct	4 ms	12892 KB	Output is correct
8	Correct	4 ms	13144 KB	Output is correct
9	Correct	4 ms	12888 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct
11	Correct	3 ms	12892 KB	Output is correct
12	Correct	4 ms	12892 KB	Output is correct
13	Correct	4 ms	12892 KB	Output is correct
14	Runtime error	13 ms	25948 KB	Execution killed with signal 11
15	Halted	0 ms	0 KB	-

Submission #883090

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 29.0

Subtask #3 9.0 / 9.0

Subtask #4 0 / 9.0

Subtask #5 0 / 9.0

Subtask #6 0 / 9.0

Subtask #7 0 / 27.0

Subtask #1
0 / 8.0

Subtask #2
0 / 29.0

Subtask #3
9.0 / 9.0

Subtask #4
0 / 9.0

Subtask #5
0 / 9.0

Subtask #6
0 / 9.0

Subtask #7
0 / 27.0