oj.uz

Submission #639547

# Submission time Handle Problem Language Result Execution time Memory
639547 2022-09-10T15:15:01 Z finn__ trapezoid (balkan11_trapezoid) C++17
28 / 100
 209 ms 26156 KB 
#include <bits/stdc++.h>
using namespace std;

#define MOD 30013

// 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] = (c[k] + u) % MOD;
                cz[k] = (cz[k] + u) % MOD;
            }
        }
        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 % MOD);
        }
    }

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

Subtask #1
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Partially correct
2 Partially correct 1 ms 340 KB Partially correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 3 ms 468 KB Partially correct
5 Incorrect 3 ms 724 KB Output isn't correct
6 Partially correct 5 ms 1048 KB Partially correct
7 Partially correct 9 ms 1172 KB Partially correct
8 Incorrect 8 ms 1616 KB Output isn't correct
9 Partially correct 16 ms 3024 KB Partially correct
10 Partially correct 31 ms 5616 KB Partially correct
11 Partially correct 41 ms 6744 KB Partially correct
12 Incorrect 99 ms 13216 KB Output isn't correct
13 Incorrect 109 ms 14632 KB Output isn't correct
14 Partially correct 161 ms 20308 KB Partially correct
15 Incorrect 143 ms 20936 KB Output isn't correct
16 Incorrect 168 ms 21852 KB Output isn't correct
17 Partially correct 209 ms 22432 KB Partially correct
18 Partially correct 157 ms 24672 KB Partially correct
19 Partially correct 175 ms 25360 KB Partially correct
20 Partially correct 201 ms 26156 KB Partially correct