oj.uz

Submission #889475

# Submission time Handle Problem Language Result Execution time Memory
889475 2023-12-19T19:42:06 Z borisAngelov trapezoid (balkan11_trapezoid) C++17
43 / 100
 122 ms 24568 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 = 1; i <= n; ++i)
    {
        dp[i].first = 0;
        dp[i].second = 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: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
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2396 KB Partially correct
2 Correct 1 ms 2524 KB Output is correct
3 Partially correct 1 ms 2464 KB Partially correct
4 Partially correct 1 ms 2648 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 3568 KB Partially correct
9 Partially correct 10 ms 4628 KB Partially correct
10 Partially correct 19 ms 6932 KB Partially correct
11 Partially correct 25 ms 7444 KB Partially correct
12 Partially correct 57 ms 13572 KB Partially correct
13 Partially correct 67 ms 14336 KB Partially correct
14 Partially correct 107 ms 20204 KB Partially correct
15 Partially correct 92 ms 21756 KB Partially correct
16 Partially correct 100 ms 20984 KB Partially correct
17 Partially correct 107 ms 21928 KB Partially correct
18 Partially correct 83 ms 24308 KB Partially correct
19 Partially correct 109 ms 23548 KB Partially correct
20 Partially correct 122 ms 24568 KB Partially correct