제출 #892198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
892198		vjudge1	Team Contest (JOI22_team)	C++17	0 / 100	34 ms	9892 KiB

team

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

struct Fenw{
    vector <int> fenw;
    int n;
    Fenw(int n) : fenw(n + 1, 0), n(n) {}
    void upd(int i, int val){
        for (; i <= n; i += i & -i ){
            chmax(fenw[i], val);
        }
    }
    int get(int i){
        int cnt = 0;
        for (; i > 0; i -= i & -i ){
            chmax(cnt, fenw[i]);
        }
        return cnt;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <int> X(n), Y(n), Z(n), p(n), pos;
    for ( int i = 0; i < n; i++ ){
        cin >> X[i] >> Y[i] >> Z[i];
        pos.pb(Y[i]);
        p[i] = i;
    }
    sort(all(pos));
    pos.resize(unique(all(pos)) - pos.begin());
    sort(all(p), [&](int &u, int &v){
         return X[u] < X[v];
    });
    auto get = [&](int x){
        return lower_bound(all(pos), x) - pos.begin() + 1;
    };
    const int inf = 1e16;
    vector <ar<int,2>> pf(n, {-inf, -1});
    Fenw fn(n);
    for ( int i = 0; i < n; i++ ){
        int q = fn.get(get(Y[p[i]]) - 1);
        if ( i ) pf[i] = pf[i - 1];
        if ( q > Z[p[i]] ){
            chmax(pf[i], ar<int,2>{q + Y[p[i]], Y[p[i]]});
        }
        fn.upd(get(Y[p[i]]), Z[p[i]]);
    }
    int opt = -1;
    for ( int i = 0; i < n;){
        int j = i;
        while ( j < n && X[p[i]] == X[p[j]] ){
            if ( i > 0 ){
                int y = pf[i - 1][1], z = pf[i - 1][0] - y;
                if ( y > Y[p[j]] && z > Z[p[j]] ){
                    chmax(opt, z + y + X[p[j]]);
                }
            } ++j;
        } i = j;
    }
    cout << opt;

    cout << '\n';
}

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