Submission #1239818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239818		wenbang	Lasers (NOI19_lasers)	C++20	0 / 100	46 ms	22228 KiB

lasers

#include <iostream>
#include <vector>

#ifdef LOCAL
#include "print.h"
#else
template <typename... Args> inline void print(const Args&... args) {}
inline void                             newline() {}
#endif

using ll = long long;
#define endl      '\n'
#define FOR(i, n) for (int i = 0; i < n; i++)

using namespace std;

#define time first
#define type second
#define int  ll

vector<pair<int, int>> merge(vector<pair<int, int>> intervals) {
    if (intervals.empty()) {
        return {};
    }
    // sort(intervals.begin(), intervals.end());
    vector<pair<int, int>> merged;
    merged.push_back(intervals [0]);
    for (int i = 1; i < intervals.size(); i++) {
        auto& last = merged.back();
        if (last.second + 1 >= intervals [i].first) {
            last.second = max(last.second, intervals [i].second);
        }
        else {
            merged.push_back(intervals [i]);
        }
    }
    return merged;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    int length, numrows;
    cin >> length >> numrows;
    vector<vector<int>> rows;
    vector<vector<int>> rowPrefixes;
    FOR(_, numrows) {
        int x;
        cin >> x;
        vector<int> row(x), prefix(x + 1, 1);
        FOR(j, x) {
            cin >> row [j];
            prefix [j + 1] = prefix [j] + row [j];
        }
        rows.push_back(row);
        rowPrefixes.push_back(prefix);
    }
    print(rows, rowPrefixes);
    vector<vector<pair<int, int>>> uncovered(numrows);
    FOR(i, numrows) {
        const auto& prefix = rowPrefixes [i];
        FOR(j, prefix.size() - 1) {
            uncovered [i].push_back(
                {prefix [j], length - (prefix.back() - prefix [j])}
            );
        }
        uncovered [i].push_back({prefix.back(), length});
        uncovered [i] = merge(uncovered [i]);
    }
    print(uncovered);
    vector<pair<int, int>> events;
    FOR(i, numrows) {
        for (const auto& interval: uncovered [i]) {
            events.push_back({interval.first, 1});
            events.push_back({interval.second, -1});
        }
    }
    sort(
        events.begin(), events.end(),
        [](const pair<int, int>& a, const pair<int, int>& b) {
            if (a.time == b.time) {
                return a.type > b.type;
            }
            return a.time < b.time;
        }
    );
    print(events);
    vector<pair<int, int>> allUncovered;
    int                    count    = 0;
    int                    lastTime = -1;
    for (const auto& event: events) {
        count += event.type;
        if (count == numrows - 1) {
            if (lastTime != -1 && lastTime != event.time) {
                allUncovered.push_back({lastTime, event.time});
            }
        }
        lastTime = event.time;
    }
    print(allUncovered);
    int ans = 0;
    for (const auto& interval: allUncovered) {
        ans += interval.second - interval.first + 1;
    }
    cout << length - ans << endl;
}

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