Submission #1166987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166987		chikien2009	Team Contest (JOI22_team)	C++20	100 / 100	886 ms	32116 KiB

team

#include <bits/stdc++.h>

using namespace std;

inline void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

class SEGMENT_TREE
{
    private:
    int tree_size;
    vector<int> tree_min, tree_max;

    inline void Update(int ind, int l, int r, int x, int v)
    {
        if (r < x || x < l)
        {
            return;
        }
        if (l == r)
        {
            tree_min[ind] = min(tree_min[ind], v);
            tree_max[ind] = max(tree_max[ind], v);
            return;
        }
        int m = (l + r) >> 1;
        Update(ind << 1, l, m, x, v);
        Update(ind << 1 | 1, m + 1, r, x, v);
        tree_min[ind] = min(tree_min[ind << 1], tree_min[ind << 1 | 1]);
        tree_max[ind] = max(tree_max[ind << 1], tree_max[ind << 1 | 1]);
    }
    inline int Get(int ind, int l, int r, int x, int y, bool mode)
    {
        if (r < x || y < l)
        {
            return (mode ? 1e9 : -1e9);
        }
        if (x <= l && r <= y)
        {
            return (mode ? tree_min[ind] : tree_max[ind]);
        }
        int m = (l + r) >> 1;
        if (mode)
        {
            return min(Get(ind << 1, l, m, x, y, mode), Get(ind << 1 | 1, m + 1, r, x, y, mode));
        }
        return max(Get(ind << 1, l, m, x, y, mode), Get(ind << 1 | 1, m + 1, r, x, y, mode));
    }
    public:
    inline SEGMENT_TREE(int new_size)
    {
        tree_size = new_size;
        tree_min.resize(tree_size << 2, 1e9);
        tree_max.resize(tree_size << 2, -1e9);
    }
    inline void Update(int x, int v)
    {
        Update(1, 1, tree_size, x, v);
    }
    inline int GetMin(int x, int y)
    {
        return Get(1, 1, tree_size, x, y, 1);
    }
    inline int GetMax(int x, int y)
    {
        return Get(1, 1, tree_size, x, y, 0);
    }
} st1(450000), st2(450000);

struct BEAVER
{
    int X, Y, Z;
};

int n, m, b[450000], l, r, mid, x, res = -1, c, d, e;
BEAVER a[150000];

inline bool comp(const BEAVER & ina, const BEAVER & inb)
{
    return ina.X < inb.X;
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i].X >> a[i].Y >> a[i].Z;
        b[i * 3] = a[i].X;
        b[i * 3 + 1] = a[i].Y;
        b[i * 3 + 2] = a[i].Z;
    }
    sort(a, a + n, comp);
    sort(b, b + 3 * n);
    m = unique(b, b + 3 * n) - b;
    for (int i = 0, j = 0; i < n; ++i)
    {
        a[i].X = lower_bound(b, b + m, a[i].X) - b + 1;
        a[i].Y = lower_bound(b, b + m, a[i].Y) - b + 1;
        a[i].Z = lower_bound(b, b + m, a[i].Z) - b + 1;
        while (a[i].X != a[j].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 = 450000;
            x = -1;
            while (l <= r)
            {
                e = (l + r) >> 1;
                if (st1.GetMin(e, 450000) < a[j].Z)
                {
                    x = e;
                    l = e + 1;
                }
                else
                {
                    r = e - 1;
                }
            }
            if (x != -1)
            {
                st2.Update(x, a[j].Z);
            }
            j++;
        }
        l = a[i].Y + 1;
        r = 450000;
        x = -1;
        while (l <= r)
        {
            e = (l + r) >> 1;
            if (st2.GetMax(e, 450000) > a[i].Z)
            {
                x = e;
                l = e + 1;
            }
            else
            {
                r = e - 1;
            }
        }
        if (x != -1)
        {
            res = max(res, b[a[i].X - 1] + b[x - 1] + b[st2.GetMax(x, 450000) - 1]);
        }
    }
    cout << res;
    return 0;
}

• 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