Submission #883049

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
883049	2023-12-04T12:47:29 Z	LucaIlie	Team Contest (JOI22_team)	C++17	0 / 100	270 ms	15196 KB

team

#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 ) {
        if ( a.a == b.a )
            return a.b < b.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 );
    }
    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++ ) {
        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( normB[v[i].b] + 1, normC[v[i].c] + 1 ) );
        for ( int i = l; i < r; i++ ) {
            aib2d.updateInv( normB[v[i].b], normC[bestC[i]], v[i].b + bestC[i] );
            aib2d.updateInv( normB[bestB[i]], normC[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	5 ms	14936 KB	Output is correct
2	Correct	5 ms	14940 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	14976 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	6 ms	15196 KB	Output is correct
11	Correct	4 ms	14940 KB	Output is correct
12	Correct	4 ms	14940 KB	Output is correct
13	Correct	4 ms	14948 KB	Output is correct
14	Incorrect	6 ms	15196 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	14936 KB	Output is correct
2	Correct	5 ms	14940 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	14976 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	6 ms	15196 KB	Output is correct
11	Correct	4 ms	14940 KB	Output is correct
12	Correct	4 ms	14940 KB	Output is correct
13	Correct	4 ms	14948 KB	Output is correct
14	Incorrect	6 ms	15196 KB	Output isn't correct
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	14968 KB	Output is correct
3	Correct	4 ms	14936 KB	Output is correct
4	Correct	5 ms	14940 KB	Output is correct
5	Correct	5 ms	14940 KB	Output is correct
6	Correct	5 ms	14940 KB	Output is correct
7	Correct	5 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	5 ms	14940 KB	Output is correct
11	Correct	270 ms	14956 KB	Output is correct
12	Incorrect	186 ms	14948 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	14968 KB	Output is correct
3	Correct	4 ms	14936 KB	Output is correct
4	Correct	5 ms	14940 KB	Output is correct
5	Correct	5 ms	14940 KB	Output is correct
6	Correct	5 ms	14940 KB	Output is correct
7	Correct	5 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	5 ms	14940 KB	Output is correct
11	Correct	270 ms	14956 KB	Output is correct
12	Incorrect	186 ms	14948 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	14968 KB	Output is correct
3	Correct	4 ms	14936 KB	Output is correct
4	Correct	5 ms	14940 KB	Output is correct
5	Correct	5 ms	14940 KB	Output is correct
6	Correct	5 ms	14940 KB	Output is correct
7	Correct	5 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	5 ms	14940 KB	Output is correct
11	Correct	270 ms	14956 KB	Output is correct
12	Incorrect	186 ms	14948 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	14968 KB	Output is correct
3	Correct	4 ms	14936 KB	Output is correct
4	Correct	5 ms	14940 KB	Output is correct
5	Correct	5 ms	14940 KB	Output is correct
6	Correct	5 ms	14940 KB	Output is correct
7	Correct	5 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	5 ms	14940 KB	Output is correct
11	Correct	270 ms	14956 KB	Output is correct
12	Incorrect	186 ms	14948 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #7
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	14936 KB	Output is correct
2	Correct	5 ms	14940 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	14976 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	6 ms	15196 KB	Output is correct
11	Correct	4 ms	14940 KB	Output is correct
12	Correct	4 ms	14940 KB	Output is correct
13	Correct	4 ms	14948 KB	Output is correct
14	Incorrect	6 ms	15196 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Submission #883049

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 29.0

Subtask #3 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
0 / 9.0

Subtask #4
0 / 9.0

Subtask #5
0 / 9.0

Subtask #6
0 / 9.0

Subtask #7
0 / 27.0