Submission #1138190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138190		fzyzzz_z	Team Contest (JOI22_team)	C++20	0 / 100	0 ms	324 KiB

team

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

using ll = long long;

void print(array<int,3> v) {
    cout << v[0] << ' ' << v[1] << ' ' << v[2] << '\n'; 
}
void clean(vector<array<int, 3>> & v) {
    vector<array<int, 3>> res; 
    int n = v.size(); 
    vector<int> yes(n, 1); 
    for (int t = 0; t < 3; ++t) {
        map<vector<int>, vector<int>> f; 
        for (int i = 0; i < n; ++i) {
            vector<int> x, y; 
            for (int j = 0; j < 3; ++j) {
                if (j == t) y.push_back(v[i][j]); 
                else x.push_back(v[i][j]); 
            }
            f[x].push_back(y[0]); 
        }
        for (auto & [x, y]: f) sort(y.begin(), y.end()); 
        for (int i = 0; i < n; ++i) {
            vector<int> x; 
            for (int j = 0; j < 3; ++j) {
                if (j != t) x.push_back(v[i][j]); 
            }
            if (v[i][t] != f[x][0] && v[i][t] != f[x].back()) {
                yes[i] = 0; 
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (yes[i]) {
            res.push_back(v[i]); 
            // cout << v[i][0] << ' ' << v[i][1] << ' ' << v[i][2] << '\n'; 
        }
    }
    v = res; 
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; 
    cin >> n; 
    map<int, vector<pair<int, int>>> f; 
    set<array<int, 3>> seen; 
    vector<array<int, 3>> v; 
    for (int i = 0; i < n; ++i) {
        int x, y, z; 
        cin >> x >> y >> z; 
        // if (seen.find({x, y, z}) != seen.end()) continue; 
        // seen.insert({x, y, z}); 
        v.push_back({x, y, z}); 
    }
    
    // clean(v); 

    // n = v.size(); 
    // for (int i = 0; i < n; ++i) {
    //     for (int j = i + 1; j < n; ++j) {
    //         for (int k = j + 1; k < n; ++k) {
    //             vector<int> z{0, 1, 2}; 
    //             do {
    //                 if (v[i][z[0]] > max(v[j][z[0]], v[k][z[0]])) {
    //                     if (v[j][z[1]] > max(v[i][z[1]], v[k][z[1]])) {
    //                         if (v[k][z[2]] > max(v[i][z[2]], v[j][z[2]])) {
    //                             // print(v[i]); 
    //                             // print(v[j]); 
    //                             // print(v[k]); 
    //                             // cout << (v[i][z[0]] + v[j][z[1]] + v[k][z[2]]) << '\n'; 
    //                         }
    //                     }
    //                 }
    //             } while (next_permutation(z.begin(), z.end())); 
    //         }
    //     }
    // }

    for (auto [x, y, z]: v) {
        f[x].push_back({y, z}); 
    }

    set<pair<int, int>> st, ts; 
    int sx = -1, sy = -1; 

    int ans = -1; 
    for (auto & [d1, v]: f) {
        // cout << "!!! " << d1 << "  PRE  " << sx << ' ' << sy << '\n'; 
        // for (auto [x, y]: st) {
        //     // cout << x << ' ' << y << '\n';
        //     assert(ts.find({y, x}) != ts.end()); 
        // }
        // cout << "END\n"; 
        for (auto [x, y]: v) {
            if (x < sx && y < sy) {
                ans = max(ans, d1 + sx + sy); 
            }
        }

        for (auto [x, y]: v) {
            // cout << x << ' ' << y << '\n'; 
            if (x <= sx && y <= sy) continue; 

            if (st.find({x, y}) != st.end()) continue; 
            
            auto it = st.upper_bound({x, y}); 

            if (it != st.begin()) {
                it--; 
                if ((*it).second > y) {
                    sx = x; 
                    sy = (*it).second; 
                }
            } 

            auto ti = ts.upper_bound({y, x}); 

            if (ti != ts.begin()) {
                ti--; 
                if ((*ti).second > x) {
                    sy = y; 
                    sx = (*ti).second; 
                }
            }

            st.insert({x, y});
            ts.insert({y, x}); 

            while (st.size()) {
                auto [x, y] = *st.begin(); 
                if (x <= sx && y <= sy) {
                    st.erase(st.begin()); 
                } else {
                    break; 
                }
            }
            while (ts.size()) {
                auto [y, x] = *ts.begin(); 
                if (x <= sx && y <= sy) {
                    ts.erase(ts.begin()); 
                } else {
                    break; 
                }
            }
            
        }


    }

    cout << ans << "\n"; 


    return 0;
}

• 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