Submission #1259448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259448		phtung	Lasers (NOI19_lasers)	C++20	100 / 100	118 ms	18820 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Interval = pair<ll,ll>;

vector<Interval> merge_intervals(vector<Interval> a) {
    vector<Interval> res;
    if (a.empty()) return res;
    sort(a.begin(), a.end());
    ll curL = a[0].first, curR = a[0].second;
    for (size_t i = 1; i < a.size(); ++i) {
        if (a[i].first <= curR + 1) {
            curR = max(curR, a[i].second);
        } else {
            res.emplace_back(curL, curR);
            curL = a[i].first;
            curR = a[i].second;
        }
    }
    res.emplace_back(curL, curR);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll L;
    int R;
    if (!(cin >> L >> R)) return 0;

    vector<Interval> global_forced; // collect forced intervals from all rows

    for (int row = 0; row < R; ++row) {
        int X;
        cin >> X;
        vector<ll> W(X);
        for (int i = 0; i < X; ++i) cin >> W[i];

        // prefix sums P_m (P_0 = 0,...,P_X = T)
        vector<ll> P(X+1, 0);
        for (int i = 1; i <= X; ++i) P[i] = P[i-1] + W[i-1];
        ll T = P[X];

        // collect avoidable intervals [P_m+1, L - (T - P_m)]
        vector<Interval> avoid;
        for (int m = 0; m <= X; ++m) {
            ll l = P[m] + 1;
            ll r = L - (T - P[m]);
            if (l <= r) {
                // clamp to [1,L] although l,r already in that range logically
                if (r < 1 || l > L) continue;
                l = max<ll>(l, 1);
                r = min<ll>(r, L);
                if (l <= r) avoid.emplace_back(l, r);
            }
        }

        // merge avoid intervals
        auto avoidm = merge_intervals(avoid);

        // complement in [1,L] -> forced intervals for this row
        ll cur = 1;
        for (auto &iv : avoidm) {
            if (cur <= iv.first - 1) {
                global_forced.emplace_back(cur, iv.first - 1);
            }
            cur = iv.second + 1;
        }
        if (cur <= L) global_forced.emplace_back(cur, L);
        // note: if avoidm is empty, forced is [1,L] (handled by cur=1 case)
    }

    // merge all forced intervals across rows and sum lengths
    auto merged = merge_intervals(global_forced);
    ll ans = 0;
    for (auto &iv : merged) {
        ans += (iv.second - iv.first + 1);
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 13 / 13