제출 #1184339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184339		Gray	Team Contest (JOI22_team)	C++20	73 / 100	2100 ms	172828 KiB

team

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

struct Fenwick2d{
    vector<map<ll, ll>> tr;
    ll offs=0, n;
    Fenwick2d(ll N){
        n=N+20; offs=10;
        tr.resize(n+1);
    }
    void add(ll _i, ll _j, ll x){
        // cout << _i << " " << _j << " +" << x << ln;
        _i+=offs; _j+=offs;
        for (ll i=_i; i; i-=(-i&i)){
            for (ll j=_j; j; j-=(-j&j)){
                tr[i][j]=max(tr[i][j], x);
            }
        }
    }
    ll get(ll _i, ll _j){
        // cout << _i << " " << _j << " get: ";
        _i+=offs; _j+=offs; ll res=-1;
        for (ll i=_i; i<=n; i+=(-i&i)){
            for (ll j=_j; j<=n; j+=(-j&j)){
                if (tr[i].count(j)) res=max(res, tr[i][j]);
            }
        }
        // cout << res << ln;
        return res;
    }
};

struct Fenwick{
    vector<ll> tr;
    ll offs, n;
    Fenwick(ll N){
        n=N+20; offs=10;
        tr.resize(n+1);
    }
    void add(ll i, ll x){
        i+=offs; for (; i<=n; i+=(-i&i)) tr[i]=max(tr[i], x);
    }
    ll get(ll i){
        i+=offs;
        ll res=-1; for (; i; i-=(-i&i)) res=max(res, tr[i]);
        return res;
    }
};

void solve(){
    ll n; cin >> n;
    map<ll, vector<pair<ll, ll>>> a;
    vector<ll> xs, ys, zs;
    vector<array<ll, 3>> vals(n);
    for (ll i=0; i<n; i++){
        ll x, y, z; cin >> x >> y >> z;
        vals[i] = {x, y, z}; xs.push_back(x);
        ys.push_back(y); zs.push_back(z);
    }
    sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(zs.begin(), zs.end()); zs.erase(unique(zs.begin(), zs.end()), zs.end());
    for (ll i=0; i<n; i++){
        ll x = lower_bound(xs.begin(), xs.end(), vals[i][0])-xs.begin();
        ll y = lower_bound(ys.begin(), ys.end(), vals[i][1])-ys.begin();
        ll z = lower_bound(zs.begin(), zs.end(), vals[i][2])-zs.begin();
        a[x].push_back({y, z});
    }

    Fenwick2d pos(n);
    Fenwick posy(n), posz(n);
    ll res=-1;
    for (auto &[x, ar]:a){
        for (auto [y, z]:ar){
            ll psx = pos.get(y+1, z+1);
            if (psx!=-1) res=max(res, psx+xs[x]);
        }
        for (auto [y, z]:ar){
            ll dz = posy.get(y-1);
            ll dy = posz.get(z-1);
            if (dz>z){
                // cout << ys[y] << "&" << zs[dz] << " at " << xs[x] << ln;
                pos.add(y, dz, ys[y]+zs[dz]);
            }
            if (dy>y){
                // cout << ys[dy] << "&" << zs[z] << " at " << xs[x] << ln;
                pos.add(dy, z, ys[dy]+zs[z]);
            }
            posy.add(y, z); posz.add(z, y);
        }
    }
    cout << res << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll c=1; c<=t; c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

• 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: 0 / 27