Submission #1171999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171999		harrylee	Team Contest (JOI22_team)	C++20	100 / 100	768 ms	32184 KiB

team

#include<bits/stdc++.h>
using namespace std;
const int maxn = 150000;

int n, l, r, m, c, res = -1;
struct beaver{
    int X, Y, Z;
};
beaver a[maxn];
vector<int> v;

struct str{
    int max, min;
    inline str(){
        max = -1e9;
        min = 1e9;
    }
};

str operator + (const str& x, const str& y){
    str ans;
    ans.max = max(x.max, y.max);
    ans.min = min(x.min, y.min);
    return ans;
}

class segment_tree{
    private:
        vector<str> st;
        int tree_size;
        void update(int id, int l, int r, int i, int val){
            if (i > r || i < l) return;
            if (l == r){
                st[id].max = max(st[id].max, val);
                st[id].min = min(st[id].min, val);
                return;
            }
            int mid = (l + r) >> 1;
            update(id * 2, l, mid, i, val);
            update(id * 2 + 1, mid + 1, r, i, val);
            st[id] = st[id * 2] + st[id * 2 + 1];
            return;
        }

        int get(int id, int l, int r, int u, int v, bool maxx){
            if (l > v || r < u){
                return (maxx ? -1e9 : 1e9);
            }
            if (l >= u && r <= v){
                return (maxx ? st[id].max : st[id].min);
            }
            int mid = (l + r) >> 1;
            if (maxx) return max(get(id * 2, l, mid, u, v, maxx), get(id * 2 + 1, mid + 1, r, u, v, maxx));
            return min(get(id * 2, l, mid, u, v, maxx), get(id * 2 + 1, mid + 1, r, u, v, maxx));
        }
    
    public:
        segment_tree(int size){
            tree_size = size;
            st.resize(tree_size << 2);
        }

        void update(int i, int val){
            update(1, 1, tree_size, i, val);
        }

        int getmax(int u, int v){
            return get(1, 1, tree_size, u, v, 1);
        }

        int getmin(int u, int v){
            return get(1, 1, tree_size, u, v, 0);
        }
};

bool comp(const beaver& x, const beaver& y){
    return (x.X < y.X);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i){
        cin >> a[i].X >> a[i].Y >> a[i].Z;
        v.push_back(a[i].X);
        v.push_back(a[i].Y);
        v.push_back(a[i].Z);
    }

    sort(v.begin(), v.end());
    auto it = unique(v.begin(), v.end());
    v.erase(it, v.end());

    int compressed_size = v.size();

    segment_tree st1(compressed_size);
    segment_tree st2(compressed_size);

    sort(a, a + n, comp);

    for (int i = 0, j = 0; i < n; ++i){
        a[i].X = lower_bound(v.begin(), v.end(), a[i].X) - v.begin() + 1;
        a[i].Y = lower_bound(v.begin(), v.end(), a[i].Y) - v.begin() + 1;
        a[i].Z = lower_bound(v.begin(), v.end(), a[i].Z) - v.begin() + 1;
        while (a[j].X != a[i].X){
            st1.update(a[j].Y, a[j].Z);
            c = st1.getmax(1, a[j].Y - 1);
            if (c > a[j].Z){
                st2.update(a[j].Y, c);
            }
            l = a[j].Y + 1;
            r = compressed_size;
            int ans = -1;
            while (l <= r){
                m = (l + r) >> 1;
                if (st1.getmin(m, compressed_size) < a[j].Z){
                    ans = m;
                    l = m + 1;
                } else r = m - 1;
            }
            if (ans != -1){
                st2.update(ans, a[j].Z);
            }
            j++;
        }
        l = a[i].Y + 1;
        r = compressed_size;
        int ans = -1;
        while (l <= r){
            m = (l + r) >> 1;
            if (st2.getmax(m, compressed_size) > a[i].Z){
                ans = m;
                l = m + 1;
            } else r = m - 1;
        }
        if (ans != -1){
            res = max(res, v[a[i].X - 1] + v[ans - 1] + v[st2.getmax(ans, compressed_size) - 1]);
        }
    }
    cout << res;
}

• 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