Submission #883118

#	Time	Username	Problem	Language	Result	Execution time	Memory
883118		LucaIlie	Team Contest (JOI22_team)	C++17	100 / 100	925 ms	34420 KiB

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;

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;

    int ans = -1, l, r;

    ///BC
    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 ) {
        return a.b < b.b;
    } );
    aib.init();
    l = r = 0;
    while ( l < n ) {
        r = l;
        while ( r < n && v[l].b == v[r].b )
            r++;
        for ( int i = l; i < r; i++ ) {
            if ( v[i].bestC > v[i].c ) {
                int a = aib.query( normC[v[i].bestC] - 1 );
                if ( a > v[i].a )
                    ans = max( ans, a + v[i].b + v[i].bestC );
            }
        }
        for ( int i = l; i < r; i++ )
            aib.update( normC[v[i].c], v[i].a );
        l = r;
    }


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

    cout << ans;

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27