Submission #1090732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090732		Evirir	Lasers (NOI19_lasers)	C++17	100 / 100	402 ms	95132 KiB

lasers

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

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
using ll = long long;
using ld = long double;
using ii = pair<int, int>;

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

    int w,h; cin>>w>>h;
    vector<vector<int>> a(h);
    forn(i,0,h)
    {
        int n; cin>>n;
        a[i].reserve(n);
        forn(j,0,n)
        {
            int x; cin>>x;
            a[i].pb(x);
        }
    }

    vector<vector<ii>> rs(h);
    forn(rid,0,h)
    {
        auto& v = a[rid];
        auto& cr = rs[rid];
        ll sum = accumulate(all(v), 0);
        int l = 0, r = w - sum - 1;
        cr.pb({l, r});
        for (const auto x : v)
        {
            l += x;
            r += x;
            if (l <= cr.back().S + 1)
            {
                auto [l0, r0] = cr.back();
                cr.pop_back();
                cr.pb({l0, r});
            }
            else
            {
                cr.pb({l, r});
            }
        }
    }

    vector<ii> eve;
    set<int> ps;
    for (const auto& cr : rs)
    {
        for (const auto& [l, r] : cr)
        {
            eve.pb({l, 1});
            eve.pb({r + 1, -1});
            ps.insert(l);
            ps.insert(r + 1);
        }
    }

    sort(all(eve), greater<>());
    int last = -1;
    int cnt = 0;
    int ans = 0;
    for (const auto p : ps)
    {
        while (!eve.empty() && eve.back().F == p)
        {
            int t = eve.back().S;
            eve.pop_back();
            cnt += t;
        }
        if (cnt != h && last != -1)
        {
            ans += p - last;
            last = -1;
        }
        if (cnt == h)
            last = p;
    }
    cout << w - 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