oj.uz

Submission #889477

# Submission time Handle Problem Language Result Execution time Memory
889477 2023-12-19T19:44:09 Z borisAngelov trapezoid (balkan11_trapezoid) C++17
40 / 100
 121 ms 25452 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int mod = 30013;

int n;

struct Segment
{
    int x;
    int y;
};

bool cross(const Segment& fr, const Segment& sc)
{
    return fr.x <= sc.y && fr.y >= sc.x;
}

struct Trapezoid
{
    Segment up;
    Segment down;
};

Trapezoid a[maxn];

pair<long long, long long> dp[maxn];

struct Event
{
    int upPos;
    int downPos;
    int type;
    int idx;

    Event()
    {

    }

    Event(int _upPos, int _downPos, int _type, int _idx)
    {
        upPos = _upPos;
        downPos = _downPos;
        type = _type;
        idx = _idx;
    }

    bool operator < (const Event& other) const
    {
        return upPos < other.upPos;
    }
};

vector<Event> events;

unordered_map<int, int> compressedValues;
vector<int> toCompress;

struct Node
{
    long long maxLength;
    long long cnt;

    Node()
    {

    }

    Node(long long _maxLength, long long _cnt)
    {
        maxLength = _maxLength;
        cnt = _cnt;
    }
};

struct SegmentTree
{
    Node tree[8 * maxn];

    Node combine(Node lhs, Node rhs)
    {
        if (lhs.maxLength < rhs.maxLength)
        {
            return rhs;
        }

        if (rhs.maxLength < lhs.maxLength)
        {
            return lhs;
        }

        return Node(lhs.maxLength, (lhs.cnt + rhs.cnt) % mod);
    }

    void update(int node, int l, int r, int pos, pair<long long, long long> val)
    {
        if (l == r)
        {
            tree[node] = combine(tree[node], Node(val.first, val.second));
            return;
        }

        int mid = (l + r) / 2;

        if (pos <= mid)
        {
            update(2 * node, l, mid, pos, val);
        }
        else
        {
            update(2 * node + 1, mid + 1, r, pos, val);
        }

        tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
    }

    Node query(int node, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr)
        {
            return tree[node];
        }

        int mid = (l + r) / 2;

        Node result = Node(0, 1);

        if (ql <= mid)
        {
            result = combine(result, query(2 * node, l, mid, ql, qr));
        }

        if (qr >= mid + 1)
        {
            result = combine(result, query(2 * node + 1, mid + 1, r, ql, qr));
        }

        return result;
    }

    void update(int pos, pair<long long, long long> val)
    {
        update(1, 1, 2 * n, pos, val);
    }

    pair<long long, long long> query(int l, int r)
    {
        Node res = query(1, 1, 2 * n, l, r);
        return make_pair(res.maxLength, res.cnt);
    }
};

SegmentTree tree;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].up.x >> a[i].up.y >> a[i].down.x >> a[i].down.y;
    }

    sort(a + 1, a + n + 1, [&](const Trapezoid& fr, const Trapezoid& sc)
    {
        return fr.down.x < sc.down.x;
    });

    for (int i = 1; i <= n; ++i)
    {
        events.push_back(Event(a[i].up.x, a[i].down.x, 1, i));
        events.push_back(Event(a[i].up.y, a[i].down.y, 2, i));
        toCompress.push_back(a[i].down.x);
        toCompress.push_back(a[i].down.y);
    }

    sort(toCompress.begin(), toCompress.end());

    int currNumber = 0;

    for (int i = 0; i < toCompress.size(); ++i)
    {
        if (i == 0 || toCompress[i] != toCompress[i - 1])
        {
            ++currNumber;
        }

        compressedValues[toCompress[i]] = currNumber;
    }

    sort(events.begin(), events.end());

    pair<long long, long long> result = make_pair(0, 1);

    for (int i = 1; i <= n; ++i)
    {
        dp[i].first = 0;
        dp[i].second = 0;
    }

    for (int i = 0; i < events.size(); ++i)
    {
        int up = events[i].upPos;
        int down = compressedValues[events[i].downPos];
        int type = events[i].type;
        int idx = events[i].idx;

        if (type == 1) // calculate
        {
            if (down >= 2)
            {
                dp[idx] = tree.query(1, down - 1);
            }

            ++dp[idx].first;

            //cout << idx << " :: " << dp[idx].first << endl;

            if (result.first < dp[idx].first)
            {
                result.first = dp[idx].first;
                result.second = dp[idx].second;
            }
            else if (result.first == dp[idx].first)
            {
                result.second += dp[idx].second;
                result.second %= mod;
            }
        }
        else // add up to tree
        {
            tree.update(down, dp[idx]);
        }
    }

    cout << result.first << ' ' << result.second << endl;

    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:193:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |     for (int i = 0; i < toCompress.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~
trapezoid.cpp:213:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |     for (int i = 0; i < events.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~
trapezoid.cpp:215:13: warning: unused variable 'up' [-Wunused-variable]
  215 |         int up = events[i].upPos;
      |             ^~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2396 KB Partially correct
2 Partially correct 1 ms 2396 KB Partially correct
3 Partially correct 1 ms 2580 KB Partially correct
4 Partially correct 1 ms 2652 KB Partially correct
5 Partially correct 2 ms 2652 KB Partially correct
6 Partially correct 3 ms 3164 KB Partially correct
7 Partially correct 4 ms 3164 KB Partially correct
8 Partially correct 5 ms 3612 KB Partially correct
9 Partially correct 10 ms 4628 KB Partially correct
10 Partially correct 19 ms 6932 KB Partially correct
11 Partially correct 26 ms 7444 KB Partially correct
12 Partially correct 56 ms 13524 KB Partially correct
13 Partially correct 72 ms 14592 KB Partially correct
14 Partially correct 86 ms 19708 KB Partially correct
15 Partially correct 91 ms 20220 KB Partially correct
16 Partially correct 108 ms 20728 KB Partially correct
17 Partially correct 117 ms 22012 KB Partially correct
18 Partially correct 89 ms 25452 KB Partially correct
19 Partially correct 109 ms 23164 KB Partially correct
20 Partially correct 121 ms 24780 KB Partially correct