Submission #711311

#	Time	Username	Problem	Language	Result	Execution time	Memory
711311		kostia244	Team Contest (JOI22_team)	C++17	100 / 100	185 ms	15384 KiB

team

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int inf = 1<<28;

struct Fenwick {
    vector<int> f;
    Fenwick(int n) : f(n, -inf) {}
    void upd(int pos, int val) {
        for(; pos < f.size(); pos += pos & -pos)
            f[pos] = max(f[pos], val);
    }
    int get(int pos) {
        int res = -inf;
        for(; pos; pos -= pos & -pos)
            res = max(res, f[pos]);
        return res;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<array<int, 3>> a(n);
    vector<int> Y, yid(n), B(n, inf);
    Fenwick A(n + 1);
    for(auto &[x, y, z] : a) {
        cin >> x >> y >> z;
        Y.push_back(y);
    }
    sort(all(a));
    a.erase(unique(all(a)), a.end());
    sort(all(Y));
    Y.erase(unique(all(Y)), Y.end());
    for(int i = 0; i < n; i++)
        yid[i] = lower_bound(all(Y), a[i][1]) - Y.begin();
    n = a.size();

    set<int> legal_b, blocked_b;
    auto add = [&](int i) {
        int y_id = yid[i];
        int z = a[i][2];
        if(legal_b.count(y_id)) {
            legal_b.erase(y_id);
        }
        if(blocked_b.count(y_id)) {
            blocked_b.erase(y_id);
        }

        B[y_id] = min(B[y_id], z);
        A.upd(y_id + 1, z);

        int zmax = A.get(y_id);
        if(zmax > B[y_id])
            legal_b.insert(y_id);
        else
            blocked_b.insert(y_id);
        
        auto it = blocked_b.upper_bound(y_id);
        while(it != blocked_b.end()) {
            int pos = *it;
            if(B[pos] < z) {
                blocked_b.erase(pos);
                legal_b.insert(pos);
            } else 
                break;
            it = blocked_b.upper_bound(y_id);
        }
    };
    auto query = [&](int ly, int z) {
        if(legal_b.empty()) return -inf;
        int pos = *legal_b.rbegin();
        int zmax = A.get(pos);
        // cout << "cut at " << pos << " \\ " << zmax << endl;
        if(pos <= ly || zmax <= z) return -inf;
        return Y[pos] + zmax;
    };

    int ans = -1;
    for(int j = 0, i = 0; i < n; i++) {//z
        while(a[j][0] < a[i][0]) {
            add(j++);
        }
        // cout << "Ask " << a[i][0] << " " << a[i][1] << " " << a[i][2] << " " << yid[i] << endl;
        ans = max(ans, a[i][0] + query(yid[i], a[i][2]));
    }
    cout << ans << '\n';
}

Compilation message (stderr)

team.cpp: In member function 'void Fenwick::upd(int, int)':
team.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         for(; pos < f.size(); pos += pos & -pos)
      |               ~~~~^~~~~~~~~~

• 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