Submission #545057

#	Time	Username	Problem	Language	Result	Execution time	Memory
545057		baluteshih	Team Contest (JOI22_team)	C++14	100 / 100	140 ms	16048 KiB

team

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

struct Node {
    int x, y, z;
    bool operator<(const Node &a) const {
        return x > a.x;
    }
} arr[150005];

multiset<pii> yst, zst;

void insert(multiset<pii> &st, pii &mx, pii val) {
    auto p = st.lower_bound(pii(val.X, val.Y));
    while (p != st.end() && p->Y <= val.Y)
        p = st.erase(p);
    if (p == st.begin())
        st.insert(val);
    else {
        if (prev(p)->Y < val.Y)
            st.insert(val);
        else if (prev(p)->Y > val.Y) {
            if (mx.X + mx.Y < val.X + prev(p)->Y)
                mx = pii(val.X, prev(p)->Y);
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    int ans = -1;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i].x >> arr[i].y >> arr[i].z;
    sort(arr + 1, arr + n + 1);
    pii ymx = pii(-1, -1);
    pii zmx = pii(-1, -1);
    for (int i = n, j = n; i >= 1; --i) {
        while (arr[j].x < arr[i].x) {
            insert(yst, ymx, pii(arr[j].y, arr[j].z));
            insert(zst, zmx, pii(arr[j].z, arr[j].y));
            /*cout << "insert (" << arr[j].y << ", " << arr[j].z << "),\n";
            cout << "ymx = (" << ymx.X << ", " << ymx.Y << ")\n";
            cout << "zmx = (" << zmx.Y << ", " << zmx.X << ")\n";*/
            --j;
        }
        if (ymx.X > arr[i].y && ymx.Y > arr[i].z)
            ans = max(ans, arr[i].x + ymx.X + ymx.Y);
        if (zmx.X > arr[i].z && zmx.Y > arr[i].y)
            ans = max(ans, arr[i].x + zmx.X + zmx.Y);
    }
    cout << ans << "\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