Submission #491187

#	Time	Username	Problem	Language	Result	Execution time	Memory
491187		blue	Lasers (NOI19_lasers)	C++17	63 / 100	292 ms	262148 KiB

lasers

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

#define sz(x) (int(x.size()))

int main()
{
    int L, R;
    cin >> L >> R;

    vi S(1+R, 0);
    vvi blocks(1+R);

    vi delta(1+L+1, 0);


    for(int r = 1; r <= R; r++)
    {
        // cerr << "\n\n\n";
        // cerr << "layer = " << r << '\n';
        int X;
        cin >> X;

        for(int x = 1; x <= X; x++)
        {
            int Z;
            cin >> Z;
            blocks[r].push_back(Z);
            S[r] += Z;
        }

        int left_sum = 0;

        deque<pii> H;

        for(int x = 0; x <= X; x++)
        {
            // cerr << left_sum << " , " << S[r] - left_sum << " : " << left_sum + 1 << ' ' << L - (S[r] - left_sum) << '\n';
            H.push_back({left_sum + 1, L - (S[r] - left_sum)});
            if(x != X)
            {
                left_sum += blocks[r][x];
            }
        }

        while(!H.empty())
        {
            while(sz(H) >= 2 && H[sz(H) - 2].second >= H[sz(H) - 1].first)
            {
                H[sz(H) - 2].second = H[sz(H) - 1].second;
                H.pop_back();
            }

            pii h = H.back();
            delta[h.first]++;
            delta[h.second + 1]--;
            H.pop_back();
        }
    }

    int ans = 0;
    int curr = 0;

    for(int i = 1; i <= L; i++)
    {
        // cerr << delta[i] << ' ';
        curr += delta[i];
        ans += (curr < R);
        // cerr << i << " : " << curr << '\n';
    }
    // cerr << '\n';

    cout << ans << '\n';
}

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