Submission #963841

#	Time	Username	Problem	Language	Result	Execution time	Memory
963841		RaresFelix	Team Contest (JOI22_team)	C++17	100 / 100	105 ms	24452 KiB

team

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
#define int ll
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

struct om {
    int x, y, z;
};

struct AIB { /// maxim pe prefix
    int n;
    vi V;
    AIB(int N) : n(N + 1), V(N + 1, -1) {}

    void update(int p, int v) {
        ++p;
        while(p < n) {
            V[p] = max(V[p], v);
            p += p & -p;
        }
    }

    int query(int p) {
        int re = -1;
        ++p;
        while(p) {
            re = max(re, V[p]);
            p -= p & -p;
        }
        return re;
    }
};

struct Plan {
    int n;
    map<int, int> MY, MZ; /// normalizari pt coordonate

    AIB MaxY, MaxZ; /// Maximele pt coordonate, dar normalizate dupa cealalta coord

    Plan(int N, map<int, int> MY0, map<int, int> MZ0) : n(N),
        MY(MY0), MZ(MZ0), MaxY(N), MaxZ(N) {}

    ll test(int y, int z) {
        ll re = -1;
        ll v1 = MaxY.query(MZ[z] - 1); 
        if(v1 == -1 || v1 <= y) return -1;
        ll v2 = MaxZ.query(MY[y] - 1);
        if(v2 == -1 || v2 <= z) return -1;
        return v1 + v2;
    }
    void insert(int y, int z) {
        /// il leg pe y cu ceva mai mic ca el
        MaxZ.update(MY[y], z);
        MaxY.update(MZ[z], y);
    }
};


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<om> V;
    vector<pair<int, int> >  X, Y, Z;
    for(int i = 0; i < n; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        V.push_back({x, y, z});
        X.push_back({x, i});
        Y.push_back({y, i});
        Z.push_back({z, i});
    }
    sort(all(X));
    sort(all(Y));
    sort(all(Z));
    stack<int> PX, PY, PZ;
    for(auto [v, p] : X) PX.push(p);
    for(auto [v, p] : Y) PY.push(p);
    for(auto [v, p] : Z) PZ.push(p);
    vector<bool> activ(n, 1);
    while(!PX.empty() && !PY.empty() && !PZ.empty()) {
        int x = PX.top(), y = PY.top(), z = PZ.top();
        if(!activ[x]) {
            PX.pop();
            continue;
        }
        if(!activ[y]) {
            PY.pop();
            continue;
        }
        if(!activ[z]) {
            PZ.pop();
            continue;
        }

        auto [x1, y1, z1] = V[x];
        auto [x2, y2, z2] = V[y];
        auto [x3, y3, z3] = V[z];

        if(y3 == y2 || x3 == x1) {
            activ[z] = 0;
            PZ.pop();
            continue;
        }
        if(x2 == x1 || z2 == z3) {
            activ[y] = 0;
            PY.pop();
            continue;
        }
        if(y1 == y2 || z1 == z3) {
            activ[x] = 0;
            PX.pop();
            continue;
        }
        cout << x1 + y2 + z3 << "\n";
        return 0;
    }
    cout << "-1\n";
    return 0;
}

Compilation message (stderr)

team.cpp: In member function 'll Plan::test(ll, ll)':
team.cpp:57:12: warning: unused variable 're' [-Wunused-variable]
   57 |         ll re = -1;
      |            ^~

• 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