Submission #713873

#	Time	Username	Problem	Language	Result	Execution time	Memory
713873		becaido	Team Contest (JOI22_team)	C++17	73 / 100	1434 ms	389732 KiB

team

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

// want O(C + n(log))

const int SIZE = 1.5e5 + 5;

int n, ans = -1;
array<int, 3> a[SIZE];

struct LIS {
    vector<int> lis;
    void add(int x) {
        lis.pb(x);
    }
    void work() {
        sort(lis.begin(), lis.end());
        lis.erase(unique(lis.begin(), lis.end()), lis.end());
    }
    int id(int x) {
        return lower_bound(lis.begin(), lis.end(), x) - lis.begin() + 1;
    }
};

LIS lx, ly;
int bit[4005][4005];
void upd(int px, int py, int x) {
    for (; px <= n; px += px & -px) {
        for (int pos = py; pos <= n; pos += pos & -pos) {
            bit[px][pos] = max(bit[px][pos], x);
        }
    }
}
int que(int px, int py) {
    int re = 0;
    for (; px; px -= px & -px) {
        for (int pos = py; pos; pos -= pos & -pos) {
            re = max(re, bit[px][pos]);
        }
    }
    return re;
}
void small() {
    FOR (i, 1, n) lx.add(a[i][0]), ly.add(a[i][1]);
    lx.work(), ly.work();
    FOR (i, 1, n) {
        FOR (j, i + 1, n) if (a[j][0] > a[i][0] && a[i][1] > a[j][1]) {
            int val = que(lx.id(a[j][0]) - 1, ly.id(a[i][1]) - 1);
            if (val > max(a[i][2], a[j][2])) ans = max(ans, a[j][0] + a[i][1] + val);
        }
        upd(lx.id(a[i][0]), ly.id(a[i][1]), a[i][2]);
    }

    lx.lis.clear(), ly.lis.clear();
    FOR (i, 1, n) {
        swap(a[i][1], a[i][2]);
        fill(bit[i], bit[i] + n + 1, 0);
    }

    FOR (i, 1, n) lx.add(a[i][0]), ly.add(a[i][1]);
    lx.work(), ly.work();
    FOR (i, 1, n) {
        FOR (j, i + 1, n) if (a[j][0] > a[i][0] && a[i][1] > a[j][1]) {
            int val = que(lx.id(a[j][0]) - 1, ly.id(a[i][1]) - 1);
            if (val > max(a[i][2], a[j][2])) ans = max(ans, a[j][0] + a[i][1] + val);
        }
        upd(lx.id(a[i][0]), ly.id(a[i][1]), a[i][2]);
    }

    cout << ans << '\n';
}

int mnx[4005][4005], mny[4005][4005], dp[4005][4005];
int mx, my;
void C_small() {
    FOR (i, 1, n) {
        mx = max(mx, a[i][0]);
        my = max(my, a[i][1]);
    }
    FOR (i, 0, mx) FOR (j, 0, my) mnx[i][j] = mny[i][j] = INT_MAX;
    FOR (i, 1, n) {
        mnx[a[i][0]][a[i][1]] = min(mnx[a[i][0]][a[i][1]], a[i][2]);
        mny[a[i][0]][a[i][1]] = min(mny[a[i][0]][a[i][1]], a[i][2]);
        dp[a[i][0]][a[i][1]] = max(dp[a[i][0]][a[i][1]], a[i][2]);
    }
    FOR (i, 0, mx) FOR (j, 0, my) {
        if (i) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            mny[i][j] = min(mny[i][j], mny[i - 1][j]);
        }
        if (j) {
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            mnx[i][j] = min(mnx[i][j], mnx[i][j - 1]);
        }
    }
    // X2<X1, Y1<Y2
    FOR (X1, 1, mx) FOR (Y2, 1, my) {
        int val = dp[X1 - 1][Y2 - 1];
        if (val > max(mnx[X1][Y2 - 1], mny[X1 - 1][Y2])) ans = max(ans, X1 + Y2 + val);
    }
    cout << ans << '\n';
}

void solve() {
    cin >> n;
    FOR (i, 1, n) FOR (j, 0, 2) cin >> a[i][j];
    sort(a + 1, a + n + 1);

    if (n <= 4000) {
        small();
        return;
    }

    C_small();
}

int main() {
    Waimai;
    solve();
}

• 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: 0 / 27