제출 #938613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938613		Pannda	Team Contest (JOI22_team)	C++17	100 / 100	276 ms	33104 KiB

team

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("inp.inp", "r", stdin);
//    freopen("out.out", "w", stdout);

    int n;
    cin >> n;
    map<int, vector<array<int, 2>>> mp;
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        mp[z].push_back({x, y});
    }

    set<array<int, 2>> xy;
    set<array<int, 2>> yx;
    set<array<int, 2>> xy_defer;
    set<array<int, 2>> yx_defer;
    static const int INF = 1e9;

    auto add = [&](int x, int y) -> void {
        while (!xy_defer.empty()) {
            auto it = xy_defer.lower_bound(array<int, 2>{x, -INF});
            if (it == xy_defer.begin()) break;
            it--;
            auto [xx, yy] = *it;
            if (yy <= y) break;
            xy_defer.erase(it);
            yx_defer.erase({yy, xx});
            xy.insert({xx, yy});
            yx.insert({yy, xx});
        }
        while (!yx_defer.empty()) {
            auto it = yx_defer.lower_bound(array<int, 2>{y, -INF});
            if (it == yx_defer.begin()) break;
            it--;
            auto [yy, xx] = *it;
            if (xx <= x) break;
            yx_defer.erase(it);
            xy_defer.erase({xx, yy});
            xy.insert({xx, yy});
            yx.insert({yy, xx});
        }
        bool should_insert;
        if (xy.empty()) {
            should_insert = false;
        } else {
            int xx = (*xy.rbegin())[0];
            int yy = (*yx.rbegin())[0];
            if (xx > x || yy > y) {
                should_insert = true;
            } else {
                should_insert = false;
            }
        }
        if (should_insert) {
            xy.insert({x, y});
            yx.insert({y, x});
        } else {
            xy_defer.insert({x, y});
            yx_defer.insert({y, x});
        }
    };

    auto query = [&](int x, int y) -> int {
        if (xy.empty()) return -INF;
        int xx = (*xy.rbegin())[0];
        int yy = (*yx.rbegin())[0];
        if (xx <= x || yy <= y) return -INF;
        return xx + yy;
    };

    int res = -1;
    for (auto [z, xy] : mp) {
        for (auto [x, y] : xy) {
            res = max(res, z + query(x, y));
        }
        for (auto [x, y] : xy) {
            add(x, y);
        }
    }
    cout << res << '\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