Submission #740603

#	Time	Username	Problem	Language	Result	Execution time	Memory
740603		finn__	Sweeping (JOI20_sweeping)	C++17	0 / 100	2003 ms	546168 KiB

sweeping

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

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

#define M 500000
#define Q 1000000

struct triangle
{
    Tree<array<uint32_t, 3>> x, y;
    uint32_t a, b;
};

uint32_t p[M][2], ind[M], l;
triangle tr[Q + 1];
bool compare_mode = 1;

bool compare_triangle(size_t const &a, size_t const &b)
{
    return !compare_mode ? tr[a].a < tr[b].a : tr[a].b > tr[b].b;
};

set<size_t, decltype(&compare_triangle)> s;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    size_t n, m, q;
    cin >> n >> m >> q;
    for (uint32_t i = 0; i < m; ++i)
    {
        cin >> p[i][0] >> p[i][1];
        tr[0].x.insert({p[i][0], p[i][1], i});
        tr[0].y.insert({p[i][1], p[i][0], i});
    }
    s = set<size_t, decltype(&compare_triangle)>(&compare_triangle);
    s.insert(0);
    l = 1;

    while (q--)
    {
        size_t t;
        cin >> t;
        if (t == 1)
        {
            size_t i;
            cin >> i, --i;
            cout << max(p[i][0], tr[ind[i]].a) << ' ' << max(p[i][1], tr[ind[i]].b) << '\n';
        }
        else if (t == 2)
        {
            uint32_t L;
            cin >> L;
            tr[Q].b = L;
            compare_mode = 1;
            auto it = s.lower_bound(Q);
            triangle &t = tr[l++], &u = tr[*it];
            if (u.y.order_of_key({L, UINT32_MAX, UINT32_MAX}) < u.y.size() / 2)
            {
                t.a = n - L;
                t.b = u.b;
                u.b = L;
                for (auto jt = u.y.begin(); jt != u.y.end() && (*jt)[0] <= L; jt = u.y.erase(jt))
                {
                    t.x.insert({(*jt)[1], (*jt)[0], (*jt)[2]});
                    t.y.insert(*jt);
                    ind[(*jt)[2]] = l - 1;
                    u.x.erase({(*jt)[1], (*jt)[0], (*jt)[2]});
                }
            }
            else
            {
                t.a = u.a;
                u.a = n - L;
                t.b = L;
                for (auto jt = u.y.rbegin(); jt != u.y.rend() && (*jt)[0] > L;)
                {
                    t.x.insert({(*jt)[1], (*jt)[0], (*jt)[2]});
                    t.y.insert(*jt);
                    ind[(*jt)[2]] = l - 1;
                    u.x.erase({(*jt)[1], (*jt)[0], (*jt)[2]});
                    jt = u.y.erase(jt);
                    if (jt != u.y.rend())
                        --jt;
                }
            }
            s.insert(l - 1);
        }
        else if (t == 3)
        {
            uint32_t L;
            cin >> L;
            tr[Q].a = L;
            compare_mode = 0;
            auto it = prev(s.upper_bound(Q));
            triangle &t = tr[l++], &u = tr[*it];
            if (u.x.order_of_key({L, UINT32_MAX, UINT32_MAX}) < u.x.size() / 2)
            {
                t.a = u.a;
                t.b = n - L;
                u.a = L;
                for (auto jt = u.x.begin(); jt != u.x.end() && (*jt)[0] <= L; jt = u.x.erase(jt))
                {
                    t.y.insert({(*jt)[1], (*jt)[0], (*jt)[2]});
                    t.x.insert(*jt);
                    ind[(*jt)[2]] = l - 1;
                    u.y.erase({(*jt)[1], (*jt)[0], (*jt)[2]});
                }
            }
            else
            {
                t.a = L;
                t.b = u.b;
                u.b = n - L;
                for (auto jt = u.x.rbegin(); jt != u.x.rend() && (*jt)[0] > L;)
                {
                    t.y.insert({(*jt)[1], (*jt)[0], (*jt)[2]});
                    t.x.insert(*jt);
                    ind[(*jt)[2]] = l - 1;
                    u.y.erase({(*jt)[1], (*jt)[0], (*jt)[2]});
                    jt = u.x.erase(jt);
                    if (jt != u.x.rend())
                        --jt;
                }
            }
            s.insert(l - 1);
        }
        else
        {
        }
    }
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25