Submission #938599

#	Time	Username	Problem	Language	Result	Execution time	Memory
938599		Pannda	Team Contest (JOI22_team)	C++17	9 / 100	65 ms	3628 KiB

team

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    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 {
        bool popped = false;
        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});
            popped = true;
        }
        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});
            popped = true;
        }
        if (popped) {
            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: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 9 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27