Submission #1268312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268312		thanhtung11	Lasers (NOI19_lasers)	C++20	100 / 100	140 ms	35504 KiB

lasers

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64 L;
    int R;
    if(!(cin >> L >> R)) return 0;
    vector<vector<int64>> rails(R);
    int64 totalDoors = 0;
    for(int i=0;i<R;i++){
        int X; cin >> X;
        rails[i].resize(X);
        for(int j=0;j<X;j++){
            cin >> rails[i][j];
            totalDoors += 1;
        }
    }

    // For each rail, build prefix sums s in increasing order: 0, w1, w1+w2, ..., W
    // For each s produce interval [s+1, s+S] where S = L - W (if S>0)
    // Merge these intervals per rail, compute complement intervals (forced) and append to global list.

    vector<pair<int64,int64>> forcedIntervals; // collect forced intervals across all rails

    for(int i=0;i<R;i++){
        auto &w = rails[i];
        int X = (int)w.size();
        int64 W = 0;
        for(int j=0;j<X;j++) W += w[j];
        int64 S = L - W; // slack
        if (S < 0) {
            // invalid input per statement (sum widths <= L), but just in case
            S = 0;
        }
        if (S == 0) {
            // all positions [1..L] are forced by this rail
            forcedIntervals.push_back({1, L});
            continue;
        }
        // build prefix sums s
        vector<int64> pref;
        pref.reserve(X+1);
        pref.push_back(0);
        int64 cur = 0;
        for(int j=0;j<X;j++){
            cur += w[j];
            pref.push_back(cur);
        }
        // pref sorted ascending. For each s in pref produce interval [s+1, s+S]
        // clip to [1,L]
        vector<pair<int64,int64>> cover;
        cover.reserve(pref.size());
        for(int64 s : pref){
            int64 l = s + 1;
            int64 r = s + S;
            if (r < 1) continue;
            if (l > L) continue;
            l = max<int64>(l, 1);
            r = min<int64>(r, L);
            if (l <= r) cover.emplace_back(l, r);
        }
        if (cover.empty()){
            // no coverable positions -> all forced
            forcedIntervals.push_back({1,L});
            continue;
        }
        // merge cover intervals (they are already sorted by l because pref increases)
        vector<pair<int64,int64>> merged;
        merged.reserve(cover.size());
        for(auto &iv : cover){
            if (merged.empty() || iv.first > merged.back().second + 1){
                merged.push_back(iv);
            } else {
                merged.back().second = max(merged.back().second, iv.second);
            }
        }
        // complement of merged within [1..L] -> forced intervals
        int64 curL = 1;
        for(auto &iv : merged){
            if (curL < iv.first){
                forcedIntervals.emplace_back(curL, iv.first - 1);
            }
            curL = iv.second + 1;
        }
        if (curL <= L){
            forcedIntervals.emplace_back(curL, L);
        }
    }

    if (forcedIntervals.empty()){
        cout << 0 << '\n';
        return 0;
    }

    // Merge all forced intervals across rails
    sort(forcedIntervals.begin(), forcedIntervals.end());
    int64 ans = 0;
    int64 curL = forcedIntervals[0].first, curR = forcedIntervals[0].second;
    for(size_t i=1;i<forcedIntervals.size();++i){
        auto [l,r] = forcedIntervals[i];
        if (l <= curR + 1){
            curR = max(curR, r);
        } else {
            ans += (curR - curL + 1);
            curL = l; curR = r;
        }
    }
    ans += (curR - curL + 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