Submission #1304979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304979		nekolie	Team Contest (JOI22_team)	C++20	100 / 100	407 ms	33336 KiB

team

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

const int baza = (1<<18);
int d[2*baza][2], opt[4];
void akt(int i) {
    i = (i+baza)/2;
    while (i > 0)
        d[i][0] = max(d[2*i][0],d[2*i+1][0]), d[i][1] = max(d[2*i][1],d[2*i+1][1]), i >>= 1;
}
int maks(int l, int r, int t) {
    l += baza-1, r += baza+1; int w = 0;
    while (l/2 != r/2) {
        if ((l&1) == 0)
            w = max(w,d[l+1][t]);
        if ((r&1) == 1)
            w = max(w,d[r-1][t]);
        l >>= 1, r >>= 1;
    }
    return w;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, odp = -1; cin >> n;
    map<int,int> mpy, mpz; int x,y,z;
    map<int,vector<pair<int,int>>> mp;
    for (int i = 0; i < n; i++)
        cin >> x >> y >> z, mp[x].push_back({y,z}), mpy[y] = 0, mpz[z] = 0;
    int cnt = 1;
    for (auto it = mpy.begin(); it != mpy.end(); it++)
        mpy[it->first] = cnt++;
    cnt = 1;
    for (auto it = mpz.begin(); it != mpz.end(); it++)
        mpz[it->first] = cnt++;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        for (auto [a,b] : it->second) {
            if (a < opt[0] && b < opt[1])
                odp = max(odp,it->first+opt[0]+opt[1]);
            if (a < opt[2] && b < opt[3])
                odp = max(odp,it->first+opt[2]+opt[3]);
        }
        for (auto [a,b] : it->second) {
            int c = mpy[a], e = mpz[b], yz = maks(0,c-1,0), zy = maks(0,e-1,1);
            if (yz > b && a >= opt[0])
                opt[0] = a, opt[1] = yz;
            if (zy > a && b >= opt[3])
                opt[2] = zy, opt[3] = b;
            d[c+baza][0] = max(d[c+baza][0],b), akt(c), d[e+baza][1] = max(d[e+baza][1],a), akt(e);
        }
    }
    cout << odp << endl;
    return 0;
}

• 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