oj.uz

Submission #639536

# Submission time Handle Problem Language Result Execution time Memory
639536 2022-09-10T14:07:54 Z finn__ trapezoid (balkan11_trapezoid) C++17
0 / 100
 235 ms 24360 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()
{
    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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
2 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 340 KB Unexpected end of file - int32 expected
4 Incorrect 2 ms 468 KB Unexpected end of file - int32 expected
5 Incorrect 4 ms 696 KB Unexpected end of file - int32 expected
6 Incorrect 8 ms 996 KB Unexpected end of file - int32 expected
7 Incorrect 9 ms 1144 KB Unexpected end of file - int32 expected
8 Incorrect 11 ms 1432 KB Unexpected end of file - int32 expected
9 Incorrect 21 ms 2660 KB Unexpected end of file - int32 expected
10 Incorrect 41 ms 5092 KB Unexpected end of file - int32 expected
11 Incorrect 60 ms 6316 KB Unexpected end of file - int32 expected
12 Incorrect 123 ms 12216 KB Unexpected end of file - int32 expected
13 Incorrect 145 ms 13896 KB Unexpected end of file - int32 expected
14 Incorrect 174 ms 17876 KB Unexpected end of file - int32 expected
15 Incorrect 181 ms 18636 KB Unexpected end of file - int32 expected
16 Incorrect 208 ms 19496 KB Unexpected end of file - int32 expected
17 Incorrect 221 ms 20340 KB Unexpected end of file - int32 expected
18 Incorrect 207 ms 22572 KB Unexpected end of file - int32 expected
19 Incorrect 221 ms 23504 KB Unexpected end of file - int32 expected
20 Incorrect 235 ms 24360 KB Unexpected end of file - int32 expected