oj.uz

답안 #889476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
889476 2023-12-19T19:43:37 Z borisAngelov 사다리꼴 (balkan11_trapezoid) C++17
43 / 100
 116 ms 25336 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 = 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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 2392 KB Partially correct
2 Correct 1 ms 2396 KB Output is correct
3 Partially correct 1 ms 2396 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 4632 KB Partially correct
10 Partially correct 19 ms 6932 KB Partially correct
11 Partially correct 26 ms 7360 KB Partially correct
12 Partially correct 55 ms 13572 KB Partially correct
13 Partially correct 69 ms 14336 KB Partially correct
14 Partially correct 85 ms 20472 KB Partially correct
15 Partially correct 90 ms 20212 KB Partially correct
16 Partially correct 99 ms 21924 KB Partially correct
17 Partially correct 102 ms 21496 KB Partially correct
18 Partially correct 87 ms 24644 KB Partially correct
19 Partially correct 116 ms 23196 KB Partially correct
20 Partially correct 115 ms 25336 KB Partially correct