oj.uz

Submission #889318

# Submission time Handle Problem Language Result Execution time Memory
889318 2023-12-19T10:58:14 Z borisAngelov trapezoid (balkan11_trapezoid) C++17
50 / 100
 500 ms 2900 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<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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 5 ms 2396 KB Output is correct
6 Correct 9 ms 2396 KB Output is correct
7 Correct 9 ms 2396 KB Output is correct
8 Correct 19 ms 2544 KB Output is correct
9 Correct 90 ms 2568 KB Output is correct
10 Correct 269 ms 2640 KB Output is correct
11 Execution timed out 514 ms 2652 KB Time limit exceeded
12 Execution timed out 1036 ms 2552 KB Time limit exceeded
13 Execution timed out 1062 ms 2656 KB Time limit exceeded
14 Execution timed out 1027 ms 2880 KB Time limit exceeded
15 Execution timed out 1032 ms 2832 KB Time limit exceeded
16 Execution timed out 1043 ms 2768 KB Time limit exceeded
17 Execution timed out 1067 ms 2644 KB Time limit exceeded
18 Execution timed out 1032 ms 2644 KB Time limit exceeded
19 Execution timed out 1053 ms 2644 KB Time limit exceeded
20 Execution timed out 1061 ms 2900 KB Time limit exceeded