Submission #639537

#	Time	Username	Problem	Language	Result	Execution time	Memory
639537		finn__	trapezoid (balkan11_trapezoid)	C++17	40 / 100	162 ms	21660 KiB

trapezoid

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

// Supports assigning a range a new maximum value and querying
// for the maximum value in a range. Maximum updates are only
// accepted when the new value is larger than the old one.
struct segtree
{
    vector<unsigned> t, z;
    size_t l;

    segtree(size_t n)
    {
        l = 1 << (32 - __builtin_clz(n));
        t = vector<unsigned>(2 * l, 0);
        z = vector<unsigned>(2 * l, 0);
    }

    void propagate(size_t k, size_t x, size_t y)
    {
        t[2 * k] = max(t[2 * k], z[k]);
        t[2 * k + 1] = max(t[2 * k + 1], z[k]);
        z[2 * k] = max(z[2 * k], z[k]);
        z[2 * k + 1] = max(z[2 * k + 1], z[k]);

        z[k] = 0;
    }

    void update_rec(size_t i, size_t j, unsigned v, size_t k, size_t x, size_t y)
    {
        if (x > y || y < i || x > j)
            return;
        if (i <= x && y <= j)
        {
            t[k] = max(t[k], v);
            z[k] = max(z[k], v);
        }
        else
        {
            propagate(k, x, y);
            update_rec(i, j, v, 2 * k, x, (x + y) / 2);
            update_rec(i, j, v, 2 * k + 1, (x + y) / 2 + 1, y);
            t[k] = max(t[2 * k], t[2 * k + 1]);
        }
    }

    void update(size_t i, size_t j, unsigned v)
    {
        update_rec(i, j, v, 1, 0, l - 1);
    }

    unsigned range_max_rec(size_t i, size_t j, size_t k, size_t x, size_t y)
    {
        if (x > y || y < i || x > j)
            return 0;
        if (i <= x && y <= j)
            return t[k];
        else
        {
            propagate(k, x, y);
            return max(range_max_rec(i, j, 2 * k, x, (x + y) / 2), range_max_rec(i, j, 2 * k + 1, (x + y) / 2 + 1, y));
        }
    }

    unsigned range_max(size_t i, size_t j)
    {
        return range_max_rec(i, j, 1, 0, l - 1);
    }
};

struct event
{
    unsigned x;
    size_t i;
    bool start;

    bool operator<(event const &e) const
    {
        return x < e.x;
    }
};

struct trapezoid
{
    size_t i;
    unsigned a, b, c, d;
};

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

    size_t n;
    cin >> n;

    vector<trapezoid> trapezoids(n);
    vector<unsigned> ycoords;

    for (size_t i = 0; i < n; i++)
    {
        trapezoid &t = trapezoids[i];
        cin >> t.a >> t.b >> t.c >> t.d;
        t.i = i;
        ycoords.push_back(t.c);
        ycoords.push_back(t.d);
    }

    sort(ycoords.begin(), ycoords.end());
    unordered_map<unsigned, unsigned> ycompr;
    size_t z = 0;
    for (size_t i = 0; i < ycoords.size(); i++)
    {
        ycompr[ycoords[i]] = z;
        z++;
        while (i < ycoords.size() - 1 && ycoords[i + 1] == ycoords[i])
            i++;
    }

    vector<event> events;
    for (auto const &t : trapezoids)
    {
        events.push_back({t.a, t.i, 1});
        events.push_back({t.b, t.i, 0});
    }

    sort(events.begin(), events.end());
    segtree tree(ycompr.size());
    vector<unsigned> largest_until(n);

    for (event const &e : events)
    {
        unsigned c = ycompr[trapezoids[e.i].c], d = ycompr[trapezoids[e.i].d];
        if (e.start)
        {
            largest_until[e.i] = tree.range_max(c, c);
        }
        else
        {
            tree.update(d + 1, tree.l - 1, largest_until[e.i] + 1);
        }
    }

    cout << tree.range_max(0, tree.l - 1) << ' ' << 0 << '\n';
}

• Subtask 1: 40 / 100