Submission #1263337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263337		chikien2009	Team Contest (JOI22_team)	C++20	0 / 100	40 ms	22384 KiB

team

#include <bits/stdc++.h>

using namespace std;

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

struct SEGMENT_TREE
{
    int mx[1200000], mn[1200000];
    inline SEGMENT_TREE()
    {
        fill_n(mx, 1200000, -1);
        fill_n(mn, 1200000, 1e9);
    }
    inline void Update(int ind, int l, int r, int x, int v)
    {
        if (r < x || x < l)
        {
            return;
        }
        if (l == r)
        {
            mx[ind] = max(mx[ind], v);
            mn[ind] = (mn[ind] == -1 ? -1 : min(mn[ind], v));
            return;
        }
        int m = (l + r) >> 1;
        Update(ind << 1, l, m, x, v);
        Update(ind << 1 | 1, m + 1, r, x, v);
        mx[ind] = max(mx[ind << 1], mx[ind << 1 | 1]);
        mn[ind] = min(mn[ind << 1], mn[ind << 1 | 1]);
    }
    inline int Get(int ind, int l, int r, int x, int y, int mode)
    {
        if (r < x || y < l)
        {
            return (mode ? 1000000000 : -1);
        }
        if (x <= l && r <= y)
        {
            return mx[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));
    }
} st1, st2;

int n, m, b[300000], c, d, l, r, mid, res = -1;
array<int, 3> a[150000];

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        b[i << 1] = a[i][1];
        b[i << 1 | 1] = a[i][2];
    }
    sort(a, a + n);
    sort(b, b + 2 * n);
    m = unique(b, b + 2 * n) - b;
    for (int i = 0, j = 0; i < n;)
    {
        while (j < n && a[i][0] == a[j][0])
        {
            a[j][1] = lower_bound(b, b + m, a[j][1]) - b;
            a[j][2] = lower_bound(b, b + m, a[j][2]) - b;
            l = a[j][1] + 1;
            r = m - 1;
            while (l <= r)
            {
                mid = (l + r) >> 1;
                d = st1.Get(1, 0, m - 1, mid, m - 1, 0);
                if (a[j][2] < d)
                {
                    l = mid + 1;
                    res = max(res, a[j][0] + b[mid] + b[d]);    
                }
                else
                {
                    r = mid - 1;
                }
            }
            j++;
        }
        while (i < j)
        {
            c = st2.Get(1, 0, m - 1, 0, a[i][1] - 1, 0);
            if (c != -1)
            {
                st1.Update(1, 0, m - 1, a[i][1], c);
            }
            c = -1;
            l = a[i][1] + 1;
            r = m - 1;
            while (l <= r)
            {
                mid = (l + r) >> 1;
                d = st2.Get(1, 0, m - 1, mid, m - 1, 1);
                if (d != -1 && a[i][2] > d)
                {
                    c = mid;
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            }
            if (c != -1)
            {
                st1.Update(1, 0, m - 1, c, a[i][2]);
            }
            st2.Update(1, 0, m - 1, a[i][1], a[i][2]);
            i++;
        }
    }
    cout << res;
    return 0;
}

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