Submission #43435151

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

#ifdef LOCAL
    #include "debug.h"
#else
    #define dbg(...)
    #define dprint(...)
    #define debug if constexpr (false)
#endif // LOCAL

constexpr int N = 4004;
int seg_min[N][N];
pair<int, int> dp[N][N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    vector<int> cnt_right(n), cnt_left(n);
    for (int i = 0, l, r; i < q; i++) {
        cin >> l >> r, l--, r--;
        cnt_left[r]++, cnt_right[l]++;
    }

    vector<int> pref_left(n + 1), pref_right(n + 1);
    for (int i = 0; i < n; i++) {
        pref_left[i + 1] = pref_left[i] + cnt_left[i];
        pref_right[i + 1] = pref_right[i] + cnt_right[i];
    }

    seg_min[n - 1][n - 1] = 1e9;
    for (int i = 0; i < n - 1; i++) seg_min[i][i] = cnt_left[i] + cnt_right[i + 1];
    for (int d = 1; d < n; d++) {
        for (int l = 0; l + d < n; l++) {
            int r = l + d;
            seg_min[l][r] = min(seg_min[l][r - 1], seg_min[l + 1][r]);
        }
    }

    // [l, r]
    auto query = [&](int l, int r, const vector<int> &pref) {
        return r < l ? 0 : pref[r + 1] - pref[l];
    };

    for (int i = 0; i < n; i++) dp[i][i] = {-1, 0};
    constexpr int LG = 30;
    vector closest_left(n, vector<int>(LG, n));
    vector closest_right(n, vector<int>(LG, -1));
    for (int d = 1; d < n; d++) {
        for (int l = 0; l + d < n; l++) {
            int r = l + d;
            dp[l][r] = {1e9, 0};
            auto update = [&](int dep, int cnt) {
                if (dp[l][r] > pair{dep, cnt}) dp[l][r] = {dep, cnt};
            };

            if (query(l, r - 1, pref_left) + query(l + 1, r, pref_right) == 0) {
                update(-1, 0);
                dbg(l, r, dp[l][r]);
                continue;
            }

            { // process empty segs
                int mx_left = closest_left[l][1] - 1;
                assert(mx_left >= l);
                int mn_right = closest_right[r][1] + 1;
                assert(mn_right <= r);
                if (mx_left + 1 >= mn_right) {
                    update(1, 2 * seg_min[max(l, mn_right - 1)][min(r - 1, mx_left)]);
                    dbg(l, r, dp[l][r]);
                    continue;
                }
            }

            for (int ans = 0;; ans++) {
                int mx_left = closest_left[l][ans] - 1;
                int mn_right = closest_right[r][ans] + 1;
                if (mx_left + 1 < mn_right) continue;
                const int from = max(l, mn_right - 1);
                const int to = min(r - 1, mx_left);
                // [from, to]
                auto relax = [&](int mid) {
                    if (dp[l][mid].first == -1) {
                        update(dp[mid + 1][r].first + 1, dp[mid + 1][r].second);
                    } else {
                        if (dp[mid + 1][r].first == -1) {
                            update(dp[l][mid].first + 1, dp[l][mid].second);
                        } else {
                            auto [dep, cnt] = dp[l][mid];
                            if (dp[mid + 1][r].first > dep) {
                                tie(dep, cnt) = dp[mid + 1][r];
                            } else if (dp[mid + 1][r].first == dep) {
                                cnt += dp[mid + 1][r].second;
                            }
                            update(dep + 1, cnt);
                        }
                    }
                };
                relax(from);
                relax(to);
                for (int d = 1; from + d <= to && d < 7; d++) {
                    relax(from + d);
                    relax(to - d);
                }
                int mid = (from + to) / 2;
                for (int d : {0, 1, 2, 3, 4, 5}) {
                    if (mid - d >= from) relax(mid - d);
                    if (d && mid + d <= to) relax(mid + d);
                }
                // for (int mid = from; mid <= to; mid++) {
                // // for (int mid = l; mid < r; mid++) {
                //     if (dp[l][mid].first == -1) {
                //         update(dp[mid + 1][r].first + 1, dp[mid + 1][r].second);
                //     } else {
                //         if (dp[mid + 1][r].first == -1) {
                //             update(dp[l][mid].first + 1, dp[l][mid].second);
                //         } else {
                //             auto [dep, cnt] = dp[l][mid];
                //             if (dp[mid + 1][r].first > dep) {
                //                 tie(dep, cnt) = dp[mid + 1][r];
                //             } else if (dp[mid + 1][r].first == dep) {
                //                 cnt += dp[mid + 1][r].second;
                //             }
                //             update(dep + 1, cnt);
                //         }
                //     }
                // }
                dbg(l, r, dp[l][r]);
                dbg(from, to, ans);
                debug {
                    for (int i = l; i < r; i++) {
                        dbg(i, dp[l][i], dp[i + 1][r]);
                    }
                    dprint();
                }
                // assert(dp[l][r].first == ans - 1);
                break;
            }
        }
        for (int l = 0; l + d < n; l++) {
            int r = l + d;
            assert(dp[l][r].first + 2 < LG);
            for (int i = 0; i < dp[l][r].first + 2; i++) {
                closest_left[l][i] = min(closest_left[l][i], r);
                closest_right[r][i] = max(closest_right[r][i], l);
            }
        }
    }
    if (dp[0][n - 1].first == -1) {
        cout << "0 " << q << '\n';
        return 0;
    }
    assert(dp[0][n - 1].first != -1);
    cout << dp[0][n - 1].first << ' ' << dp[0][n - 1].second << '\n';
}

Submission Info

Submission Time
Task E - Segment-Tree Optimization
User Mangooste
Language C++ (GCC 9.2.1)
Score 0
Code Size 6026 Byte
Status WA
Exec Time 2107 ms
Memory 127056 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
AC × 31
WA × 19
TLE × 3
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All in-01.txt, in-02.txt, in-03.txt, in-04.txt, in-05.txt, in-06.txt, in-07.txt, in-08.txt, in-09.txt, in-10.txt, in-11.txt, in-12.txt, in-13.txt, in-14.txt, in-15.txt, in-16.txt, in-17.txt, in-18.txt, in-19.txt, in-20.txt, in-21.txt, in-22.txt, in-23.txt, in-24.txt, in-25.txt, in-26.txt, in-27.txt, in-28.txt, in-29.txt, in-30.txt, in-31.txt, in-32.txt, in-33.txt, in-34.txt, in-35.txt, in-36.txt, in-37.txt, in-38.txt, in-39.txt, in-40.txt, in-41.txt, in-42.txt, in-43.txt, in-44.txt, in-45.txt, in-46.txt, in-47.txt, in-48.txt, in-49.txt, in-50.txt, in-51.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
in-01.txt AC 1728 ms 126944 KiB
in-02.txt AC 306 ms 127056 KiB
in-03.txt TLE 2105 ms 127000 KiB
in-04.txt TLE 2107 ms 126992 KiB
in-05.txt AC 1826 ms 126940 KiB
in-06.txt WA 1624 ms 126948 KiB
in-07.txt WA 1499 ms 126880 KiB
in-08.txt WA 1630 ms 127052 KiB
in-09.txt WA 1634 ms 127012 KiB
in-10.txt WA 1831 ms 126896 KiB
in-11.txt WA 1629 ms 126972 KiB
in-12.txt WA 1634 ms 126960 KiB
in-13.txt WA 1405 ms 126968 KiB
in-14.txt WA 1491 ms 126968 KiB
in-15.txt AC 1402 ms 126892 KiB
in-16.txt AC 1622 ms 127056 KiB
in-17.txt AC 1825 ms 126992 KiB
in-18.txt AC 1824 ms 126896 KiB
in-19.txt AC 1310 ms 127016 KiB
in-20.txt WA 1498 ms 126996 KiB
in-21.txt AC 1303 ms 126992 KiB
in-22.txt AC 1311 ms 126896 KiB
in-23.txt AC 1622 ms 126968 KiB
in-24.txt WA 1580 ms 126960 KiB
in-25.txt AC 1289 ms 126932 KiB
in-26.txt WA 1604 ms 127016 KiB
in-27.txt WA 1608 ms 126992 KiB
in-28.txt TLE 2071 ms 126980 KiB
in-29.txt AC 403 ms 45144 KiB
in-30.txt AC 399 ms 45024 KiB
in-31.txt AC 298 ms 126560 KiB
in-32.txt AC 148 ms 76896 KiB
in-33.txt AC 3 ms 3452 KiB
in-34.txt AC 2 ms 3436 KiB
in-35.txt AC 18 ms 3536 KiB
in-36.txt WA 1101 ms 84568 KiB
in-37.txt WA 1736 ms 118676 KiB
in-38.txt WA 1748 ms 119012 KiB
in-39.txt AC 562 ms 51620 KiB
in-40.txt AC 459 ms 44880 KiB
in-41.txt WA 1379 ms 96532 KiB
in-42.txt AC 625 ms 54820 KiB
in-43.txt AC 1450 ms 106484 KiB
in-44.txt AC 634 ms 54932 KiB
in-45.txt WA 1216 ms 89376 KiB
in-46.txt AC 6 ms 4216 KiB
in-47.txt AC 8 ms 4972 KiB
in-48.txt WA 4 ms 4100 KiB
in-49.txt AC 4 ms 4788 KiB
in-50.txt AC 5 ms 4628 KiB
in-51.txt AC 21 ms 3516 KiB
sample-01.txt AC 2 ms 3520 KiB
sample-02.txt AC 4 ms 3524 KiB