oj.uz

Submission #883053

# Submission time Handle Problem Language Result Execution time Memory
883053 2023-12-04T13:03:09 Z LucaIlie Team Contest (JOI22_team) C++17
0 / 100
 4 ms 12892 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() {
    ifstream cin( ".in" );
    ofstream cout( ".out" );
    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 );
        if ( bestC[i] <= v[i].c )
            bestC[i] = -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 );
        if ( bestB[i] <= v[i].b )
            bestB[i] = -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++ ) {
           // if ( v[i].a + aib2d.queryInv( normB[v[i].b] + 1, normC[v[i].c] + 1 ) > ans )
                //printf( "%d %d %d\n", v[i].a, v[i].b, v[i].c );
            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 ( bestC[i] != -1 )
                aib2d.updateInv( normB[v[i].b], normC[bestC[i]], v[i].b + bestC[i] );
            if ( bestB[i] != -1 )
                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 Incorrect 4 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -