Submission #1187990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187990		pemguimn	Team Contest (JOI22_team)	C++20	100 / 100	95 ms	4804 KiB

team

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5e4 + 5, INF = 1e9 + 7;

int n;

struct ele{
    int x, y, z; 
} a[N];

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n + 5, T{});
    }
    
    void upd(int x, const T &v) {
        for (int i = x; i <= n; i += i & -i) {
            a[i] = max(a[i], v);
        }
    }
    
    T get(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = max(ans, a[i]);
        }
        return ans;
    }
    
    T get(int l, int r) {
        return get(r) - get(l - 1);
    }
    
    int kth(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 20; i >= 0; i--) {
            if (x + (1 << i) <= n && cur + a[x + (1 << i)] < k) {
                x += (1 << i);
                cur = cur + a[x];
            }
        }
        return x + 1;
    }
};

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;   

    vector<int> Y, Z;
    Z.push_back(0), Y.push_back(0);
    for(int i = 0; i < n; i++){
        cin >> a[i].x >> a[i].y >> a[i].z;
        Y.push_back(a[i].y);
        Z.push_back(a[i].z);
    }
    sort(Y.begin(), Y.end()), Y.resize(unique(Y.begin(), Y.end()) - Y.begin());
    sort(Z.begin(), Z.end()), Z.resize(unique(Z.begin(), Z.end()) - Z.begin());
    sort(a, a + n, [&](ele x, ele y){ return x.x < y.x; });
    Fenwick<int> fy(n + 1), fz(n + 1);
    fill(fy.a.begin(), fy.a.end(), -INF);
    fill(fz.a.begin(), fz.a.end(), -INF);
    int ans = -INF, j = 0;
    int z = -INF, y = -INF;
    for(int i = 0; i < n; i++){
        a[i].y = lower_bound(Y.begin(), Y.end(), a[i].y) - Y.begin();
        a[i].z = lower_bound(Z.begin(), Z.end(), a[i].z) - Z.begin();
        while(a[j].x < a[i].x){
            int zz = fy.get(a[j].y - 1), yy = fz.get(a[j].z - 1);
            if(zz > Z[a[j].z] && zz + Y[a[j].y] >= z + y) z = zz, y = Y[a[j].y];
            if(yy > Y[a[j].y] && yy + Z[a[j].z] >= z + y) z = Z[a[j].z], y = yy;
            fy.upd(a[j].y, Z[a[j].z]);
            fz.upd(a[j].z, Y[a[j].y]);
            j++;
        }
        if(z > Z[a[i].z] && y > Y[a[i].y]) ans = max(ans, a[i].x + y + z);
    }
    cout << (ans > 0 ? ans : -1) << '\n';
}

• 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