Submission #639545

#	Time	Username	Problem	Language	Result	Execution time	Memory
639545		finn__	trapezoid (balkan11_trapezoid)	C++17	10 / 100	208 ms	27196 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, c, cz;
    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);
        c = vector<unsigned>(2 * l, 1);
        cz = vector<unsigned>(2 * l, 0);
    }

    void propagate(size_t k, size_t x, size_t y)
    {
        if (t[2 * k] == z[k])
        {
            c[2 * k] += cz[k];
            cz[2 * k] += cz[k];
        }
        else if (t[2 * k] < z[k])
        {
            c[2 * k] = cz[k];
            cz[2 * k] = cz[k];
        }

        if (t[2 * k + 1] == z[k])
        {
            c[2 * k + 1] += cz[k];
            cz[2 * k + 1] += cz[k];
        }
        else if (t[2 * k + 1] < z[k])
        {
            c[2 * k + 1] = cz[k];
            cz[2 * k + 1] = cz[k];
        }

        cz[k] = 0;

        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, unsigned u, size_t k, size_t x, size_t y)
    {
        if (x > y || y < i || x > j)
            return;
        if (i <= x && y <= j)
        {
            if (v > t[k])
            {
                t[k] = v;
                c[k] = u;
                z[k] = v;
                cz[k] = u;
            }
            else if (v == t[k])
            {
                c[k] += u;
                cz[k] += u;
            }
        }
        else
        {
            propagate(k, x, y);
            update_rec(i, j, v, u, 2 * k, x, (x + y) / 2);
            update_rec(i, j, v, u, 2 * k + 1, (x + y) / 2 + 1, y);

            t[k] = max(t[2 * k], t[2 * k + 1]);
            c[k] = max(c[2 * k], c[2 * k + 1]);
        }
    }

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

    pair<unsigned, 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, 0};
        if (i <= x && y <= j)
            return {t[k], c[k]};
        else
        {
            propagate(k, x, y);
            pair<unsigned, unsigned> p1 = range_max_rec(i, j, 2 * k, x, (x + y) / 2),
                                     p2 = range_max_rec(i, j, 2 * k + 1, (x + y) / 2 + 1, y);

            if (p1.first > p2.first)
                return p1;
            else if (p2.first > p1.first)
                return p2;
            else if (p1.second > p2.second)
                return p1;
            else
                return p2;
        }
    }

    pair<unsigned, 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<pair<unsigned, 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].first + 1, largest_until[e.i].second);
        }
    }

    pair<unsigned, unsigned> p = tree.range_max(0, tree.l - 1);
    cout << p.first << ' ' << 2 * p.second << '\n';
}

• Subtask 1: 10 / 100