Submission #567806

#	Time	Username	Problem	Language	Result	Execution time	Memory
567806		hoanghq2004	Team Contest (JOI22_team)	C++14	37 / 100	289 ms	39476 KiB

team

#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 15e4 + 10;

int n;

struct dta {
    int x, y, z;
    int operator < (const dta& other) const {
        return z > other.z;
    }
} A[N];

struct SegmentTree {
    int st[N * 4];
    SegmentTree() {
        memset(st, -1, sizeof(st));
    }
    void reset() {
        memset(st, -1, sizeof(st));
    }
    void add(int id, int L, int R, int i, int val) {
        if (L == R) {
            st[id] = val;
            return;
        }
        int mid = L + R >> 1;
        if (i <= mid) add(id * 2, L, mid, i, val);
        else add(id * 2 + 1, mid + 1, R, i, val);
        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }
    int get(int id, int L, int R, int k) {
        if (st[id] <= k) return -1;
        if (L == R) return L;
        int mid = L + R >> 1;
        int ans = get(id * 2, L, mid, k);
        if (ans == -1) ans = get(id * 2 + 1, mid + 1, R, k);
        return ans;
    }
} ST[2];

struct RangeTree {
    vector <int> BIT[N];
    vector <int> dta[N];
    void fake_add(int x, int y) {
        ++x, ++y;
        for (; x < N; x += x & - x)
            dta[x].push_back(y);
    }
    void build() {
        for (int i = 0; i < N; ++i) sort(dta[i].begin(), dta[i].end()), BIT[i].assign(dta[i].size() + 10, 1e9);
    }
    void add(int x, int y, int w) {
        ++x, ++y;
        for (; x < N; x += x & - x) {
            int z = lower_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin() + 1;
            for (; z < BIT[x].size(); z += z & - z)
                BIT[x][z] = min(BIT[x][z], w);
        }
    }
    int get(int x, int y) {
        ++x, ++y;
        int ans = 1e9;
        for (; x; x -= x & - x) {
            int z = upper_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin();
            for (; z; z -= z & - z)
                ans = min(ans, BIT[x][z]);
        }
        return ans;
    }
} T;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    vector <int> X, Y;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> A[i].x >> A[i].y >> A[i].z;
        A[i].x = - A[i].x, A[i].y = - A[i].y, A[i].z = - A[i].z;
    }
    for (int i = 0; i < n; ++i) X.push_back(A[i].x), Y.push_back(A[i].y);
    sort(A, A + n);
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    for (int i = 0; i < n; ++i) {
        A[i].x = lower_bound(X.begin(), X.end(), A[i].x) - X.begin();
        A[i].y = lower_bound(Y.begin(), Y.end(), A[i].y) - Y.begin();
    }
    for (int i = 0; i < n; ++i) {
        int x = ST[0].get(1, 0, X.size() - 1, A[i].y);
        int y = ST[1].get(1, 0, Y.size() - 1, A[i].x);
        if (x != -1 && x < A[i].x) T.fake_add(x, A[i].y);
        if (y != -1 && y < A[i].y) T.fake_add(A[i].x, y);
        ST[0].add(1, 0, X.size() - 1, A[i].x, A[i].y);
        ST[1].add(1, 0, Y.size() - 1, A[i].y, A[i].x);
    }
    ST[0].reset(), ST[1].reset();
    T.build();
    int ans = 1e9;
    for (int i = 0; i < n;) {
        int j = i;
        while (j < n && A[i].z == A[j].z) ++j;
        for (int k = i; k < j; ++k) ans = min(ans, A[k].z + T.get(A[k].x - 1, A[k].y - 1));
        for (int k = i; k < j; ++k) {
            int x = ST[0].get(1, 0, X.size() - 1, A[k].y);
            int y = ST[1].get(1, 0, Y.size() - 1, A[k].x);
            if (x != -1 && x < A[k].x) T.add(x, A[k].y, X[x] + Y[A[k].y]);
            if (y != -1 && y < A[k].y) T.add(A[k].x, y, X[A[k].x] + Y[y]);
            ST[0].add(1, 0, X.size() - 1, A[k].x, A[k].y);
            ST[1].add(1, 0, Y.size() - 1, A[k].y, A[k].x);
        }
        i = j;
    }
    if (ans > 0) ans = 1;
    cout << - ans;
}

Compilation message (stderr)

team.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
team.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
team.cpp: In member function 'void SegmentTree::add(int, int, int, int, int)':
team.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int mid = L + R >> 1;
      |                   ~~^~~
team.cpp: In member function 'int SegmentTree::get(int, int, int, int)':
team.cpp:45:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int mid = L + R >> 1;
      |                   ~~^~~
team.cpp: In member function 'void RangeTree::add(int, int, int)':
team.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for (; z < BIT[x].size(); z += z & - z)
      |                    ~~^~~~~~~~~~~~~~~

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