oj.uz

Submission #639545

# Submission time Handle Problem Language Result Execution time Memory
639545 2022-09-10T15:12:30 Z finn__ trapezoid (balkan11_trapezoid) C++17
10 / 100
 208 ms 27196 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, 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Partially correct
2 Partially correct 1 ms 316 KB Partially correct
3 Partially correct 1 ms 452 KB Partially correct
4 Incorrect 2 ms 468 KB Expected int32, but "4263772160" found
5 Incorrect 3 ms 724 KB Output isn't correct
6 Incorrect 5 ms 1176 KB Expected int32, but "4294704704" found
7 Incorrect 6 ms 1352 KB Expected int32, but "4235871232" found
8 Incorrect 9 ms 1696 KB Output isn't correct
9 Partially correct 17 ms 3152 KB Partially correct
10 Incorrect 34 ms 6144 KB Expected int32, but "4291910400" found
11 Incorrect 41 ms 7432 KB Expected int32, but "4290117632" found
12 Incorrect 88 ms 14176 KB Output isn't correct
13 Incorrect 106 ms 15656 KB Output isn't correct
14 Incorrect 152 ms 21284 KB Expected int32, but "4064275904" found
15 Incorrect 147 ms 21996 KB Output isn't correct
16 Incorrect 162 ms 22824 KB Output isn't correct
17 Partially correct 167 ms 23580 KB Partially correct
18 Incorrect 157 ms 25704 KB Expected int32, but "4294812356" found
19 Incorrect 174 ms 26448 KB Expected int32, but "4278365216" found
20 Incorrect 208 ms 27196 KB Expected int32, but "4287552512" found