Submission #1132477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132477		Math4Life2020	Team Contest (JOI22_team)	C++20	100 / 100	542 ms	63820 KiB

team

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;
ll ans = -1;

map<ll,ll> xh; //x->y
map<ll,ll> xhF; //y->x
map<ll,ll> yh; //y->x
map<ll,ll> yhF; //x->y
pii pqry = {-1,-1};

bool ivp(pii p1, pii p2) {
    return (((p1.first<p2.first)&&(p1.second>p2.second))||((p1.first>p2.first)&&(p1.second<p2.second)));
}

ll qry(pii p0) { //qry to change min
    if (pqry.first==-1) {
        return INF;
    }
    if (pqry.first>p0.first && pqry.second>p0.second) {
        return (pqry.first+pqry.second);
    }
    return INF;
}

void fX(ll x1, pii padd = {-1,-1}) {
    auto A0 = xh.find(x1);
    if (A0==xh.end() || A0==xh.begin()) {
        return;
    }
    A0--;
    if ((*A0).second>=xh[x1]) {
        pii pdel = *A0;
        xh.erase(A0);
        xhF.erase(xhF.find(pdel.second));
        if (padd.first!=-1) {
            xhF[padd.second]=padd.first;
        }
        fX(x1,padd);
    }
}

void updX(pii p0) {
    ll x1 = p0.first; ll y1 = p0.second;
    auto A0 = xh.lower_bound(x1);
    if (A0==xh.end() || (*A0).second>y1) {
        if (A0!=xh.end() && (*A0).first==x1) {
            pii pdel = *A0;
            xh.erase(A0);
            xhF.erase(xhF.find(pdel.second));
        }
        xh[x1]=y1;
        xhF[y1]=x1;
        fX(x1, p0); //fix X
    }
}

void fY(ll x1, pii padd = {-1,-1}) {
    auto A0 = yh.find(x1);
    if (A0==yh.end() || A0==yh.begin()) {
        return;
    }
    A0--;
    //cout << "ftest\n";
    if ((*A0).second>=yh[x1]) {
        //cout << "f1\n";
        pii pdel = *A0;
        //cout << "wipe (fY) pdel = "<<pdel.first<<","<<pdel.second<<"\n";
        yh.erase(A0);
        yhF.erase(yhF.find(pdel.second));
        if (padd.first!=-1) {
            yhF[padd.second]=padd.first;
        }
        fY(x1, padd);
    }
}

void updY(pii p0) {
    ll x1 = p0.first; ll y1 = p0.second;
    auto A0 = yh.lower_bound(x1);
    if (A0==yh.end() || (*A0).second>y1) {
        if (A0 != yh.end() && (*A0).first==x1) {
            pii pdel = *A0;
            //cout << "wipe (updY) pdel = "<<pdel.first<<","<<pdel.second<<"\n";
            yh.erase(A0);
            yhF.erase(yhF.find(pdel.second));
        }
        yh[x1]=y1;
        yhF[y1]=x1;
        fY(x1,p0); //fix X
    }
}

void pupd(pii p0, pii pext) {
    if (!ivp(p0,pext)) {
        return;
    }
    pii pnew = {max(p0.first,pext.first),max(p0.second,pext.second)};
    assert(((pqry.first<=pnew.first)&&(pqry.second<=pnew.second))||((pqry.first>=pnew.first)&&(pqry.second>=pnew.second)));
    pqry = {max(pqry.first,pnew.first),max(pqry.second,pnew.second)};
}

set<pii> alrc; //already inserted
void upd(pii p0) { //insert into hull
    if (alrc.find(p0)!=alrc.end()) {
        return;
    }
    alrc.insert(p0);
    updX(p0);
    updY({p0.second,p0.first});
    auto A0 = xhF.lower_bound(p0.second);
    if (A0!=xhF.begin()) {
        A0--;
        //cout << "f1\n";
        pupd(p0,{(*A0).second,(*A0).first});
    }
    auto A1 = yhF.lower_bound(p0.first);
    if (A1 != yhF.begin()) {
        A1--;
        //cout << "f2\n";
        pupd(p0,{(*A1).first,(*A1).second});
    }
}

int main() {
    ll N; cin >> N;
    map<ll,vector<pii>> mxyz;
    for (ll i=0;i<N;i++) {
        ll x1,y1,z1; cin >> x1 >> y1 >> z1;
        mxyz[x1].push_back({y1,z1});
    }
    for (auto A0: mxyz) {
        ll x1 = A0.first;
        vector<pii> vyz = A0.second;
        for (pii p0: vyz) {
            ll qryV = qry(p0);
            if (qryV<INF && qryV>0) {
                ans = max(ans,x1+qryV);
            }
            //ans = max(ans,x1+qry(p0)); //*pretend* that this is now {x,y}
            //cout << "x1, qry(p0)="<<x1<<","<<qry(p0)<<"\n";
        }
        for (pii p0: vyz) {
            upd(p0);
        //     cout << "PRINT NEW CYCLE\n";
        // cout << "xh: \n";
        // for (pii p0: xh) {
        //     cout << p0.first << " " <<p0.second<<"\n";
        // }
        // cout << "yh: \n";
        // for (pii p0: yh) {
        //     cout << p0.first << " " <<p0.second<<"\n";
        // }
        // cout << "xhF: \n";
        // for (pii p0: xhF) {
        //     cout << p0.first << " " <<p0.second<<"\n";
        // }
        // cout << "yhF: \n";
        // for (pii p0: yhF) {
        //     cout << p0.first << " " <<p0.second<<"\n";
        // }
        }
        // cout << "PRINT NEW CYCLE\n";
        // cout << "xh: \n";
        // for (pii p0: xh) {
        //     cout << p0.first << " " <<p0.second<<"\n";
        // }
        // cout << "yh: \n";
        // for (pii p0: yh) {
        //     cout << p0.first << " " <<p0.second<<"\n";
        // }
        // cout << "xhF: \n";
        // for (pii p0: xhF) {
        //     cout << p0.first << " " <<p0.second<<"\n";
        // }
        // cout << "yhF: \n";
        // for (pii p0: yhF) {
        //     cout << p0.first << " " <<p0.second<<"\n";
        // }
    }
    if (ans == INF) {
        cout << "-1\n";
    } else {
        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