oj.uz

Submission #639537

# Submission time Handle Problem Language Result Execution time Memory
639537 2022-09-10T14:08:43 Z finn__ trapezoid (balkan11_trapezoid) C++17
40 / 100
 162 ms 21660 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Partially correct
2 Partially correct 0 ms 340 KB Partially correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 2 ms 468 KB Partially correct
5 Partially correct 2 ms 724 KB Partially correct
6 Partially correct 4 ms 980 KB Partially correct
7 Partially correct 4 ms 1044 KB Partially correct
8 Partially correct 6 ms 1360 KB Partially correct
9 Partially correct 13 ms 2384 KB Partially correct
10 Partially correct 25 ms 4524 KB Partially correct
11 Partially correct 37 ms 5552 KB Partially correct
12 Partially correct 94 ms 10852 KB Partially correct
13 Partially correct 101 ms 12300 KB Partially correct
14 Partially correct 121 ms 15932 KB Partially correct
15 Partially correct 119 ms 16560 KB Partially correct
16 Partially correct 149 ms 17312 KB Partially correct
17 Partially correct 159 ms 18056 KB Partially correct
18 Partially correct 134 ms 20188 KB Partially correct
19 Partially correct 146 ms 20912 KB Partially correct
20 Partially correct 162 ms 21660 KB Partially correct