oj.uz

Submission #889471

# Submission time Handle Problem Language Result Execution time Memory
889471 2023-12-19T19:35:33 Z borisAngelov trapezoid (balkan11_trapezoid) C++17
40 / 100
 119 ms 26104 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, 0);

        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 = 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:207:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |     for (int i = 0; i < events.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~
trapezoid.cpp:209:13: warning: unused variable 'up' [-Wunused-variable]
  209 |         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 2396 KB Partially correct
4 Partially correct 1 ms 2540 KB Partially correct
5 Partially correct 3 ms 2908 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 12 ms 5232 KB Partially correct
10 Partially correct 19 ms 7444 KB Partially correct
11 Partially correct 26 ms 7940 KB Partially correct
12 Partially correct 59 ms 14588 KB Partially correct
13 Partially correct 68 ms 15460 KB Partially correct
14 Partially correct 86 ms 20984 KB Partially correct
15 Partially correct 114 ms 22600 KB Partially correct
16 Partially correct 116 ms 23040 KB Partially correct
17 Partially correct 106 ms 23052 KB Partially correct
18 Partially correct 83 ms 25852 KB Partially correct
19 Partially correct 111 ms 25644 KB Partially correct
20 Partially correct 119 ms 26104 KB Partially correct