Submission #889318

#	Time	Username	Problem	Language	Result	Execution time	Memory
889318		borisAngelov	trapezoid (balkan11_trapezoid)	C++17	50 / 100	1067 ms	2900 KiB

trapezoid

#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<int, int> dp[maxn];

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)
    {
        dp[i].first = 1;
        dp[i].second = 1;

        for (int j = i - 1; j >= 1; --j)
        {
            if (a[i].down.x > a[j].down.y && a[i].up.x > a[j].up.y)
            {
                //cout << i << ' ' << j << endl;

                if (dp[i].first < 1 + dp[j].first)
                {
                    dp[i].first = 1 + dp[j].first;
                    dp[i].second = dp[j].second;
                }
                else if (dp[i].first == 1 + dp[j].first)
                {
                    dp[i].second += dp[j].second;

                    if (dp[i].second >= mod)
                    {
                        dp[i].second -= mod;
                    }
                }
            }
        }
    }

    int mx = 0;
    int cnt = 0;

    for (int i = 1; i <= n; ++i)
    {
        if (mx < dp[i].first)
        {
            mx = dp[i].first;
            cnt = dp[i].second;
        }
        else if (mx == dp[i].first)
        {
            cnt += dp[i].second;

            if (cnt >= mod)
            {
                cnt -= mod;
            }
        }
    }

    cout << mx << ' ' << cnt << endl;

    return 0;
}

• Subtask 1: 50 / 100