Submission #1132246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132246		Math4Life2020	Team Contest (JOI22_team)	C++20	0 / 100	45 ms	3800 KiB

team

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

map<ll,ll> xh; //x->y
map<ll,ll> yh; //y->x
set<pii> hb; //hull of both
set<pii> hjx; //hull of just xh
set<pii> hjy; //hull of just yh

void stp(pii p0) {
    bool px = (xh.find(p0.first)!=xh.end() && xh[p0.first]==p0.second);
    bool py = (yh.find(p0.second)!=yh.end() && yh[p0.second]==p0.first);
    if (px && py) {
        hb.insert(p0);
        if (hjx.find(p0)!=hjx.end()) {
            hjx.erase(p0);
        }
        if (hjy.find(p0)!=hjy.end()) {
            hjy.erase(p0);
        }
    } else if (px && (!py)) {
        if (hb.find(p0)!=hb.end()) {
            hb.erase(p0);
        }
        hjx.insert(p0);
        if (hjy.find(p0)!=hjy.end()) {
            hjy.erase(p0);
        }
    } else if ((!px) && py) {
        if (hb.find(p0)!=hb.end()) {
            hb.erase(p0);
        }
        if (hjx.find(p0)!=hjx.end()) {
            hjx.erase(p0);
        }
        hjy.insert(p0);
    } else {
        if (hb.find(p0)!=hb.end()) {
            hb.erase(p0);
        }
        if (hjx.find(p0)!=hjx.end()) {
            hjx.erase(p0);
        }
        if (hjy.find(p0)!=hjy.end()) {
            hjy.erase(p0);
        }
    }
}

ll qry(pii p0) { //qry to change min
    ll x1 = p0.first; ll y1 = p0.second;
    if (hjx.empty() || hjy.empty()) {
        return INF;
    }
    pii px = *(--hjx.end()); pii py = *(--hjy.end());
    if (px.first>x1 && py.second>y1) {
        return px.first+py.second;
    } else {
        return INF;
    }
}

void fX(ll x1) {
    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);
        stp(pdel);
        fX(x1);
    }
}

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);
            stp(pdel);
        }
        xh[x1]=y1;
        fX(x1); //fix X
    }
}

void fY(ll x1) {
    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;
        yh.erase(A0);
        stp({pdel.second,pdel.first});
        fY(x1);
    }
}

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;
            yh.erase(A0);
            stp({pdel.second,pdel.first});
        }
        yh[x1]=y1;
        fY(x1); //fix X
    }
}

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});
    stp(p0);
}

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) {
            ans = min(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";
        // }
    }
    if (ans == INF) {
        cout << "-1\n";
    } else {
        cout << ans << "\n";
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27