Submission #491191

#	Time	Username	Problem	Language	Result	Execution time	Memory
491191		blue	Lasers (NOI19_lasers)	C++17	100 / 100	557 ms	52676 KiB

lasers

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

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

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

map<int, int> delta;

void map_insert(int u, int d)
{
    if(delta.find(u) == delta.end())
        delta[u] = d;
    else
        delta[u] += d;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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();
            map_insert(h.first, +1);
            map_insert(h.second + 1, -1);
            // delta[h.first]++;
            // delta[h.second + 1]--;
            H.pop_back();
        }
    }

    int ans = 0;

    delta.insert({1, 0});
    int curr = 0;

    int prev = -1;
    for(pii d: delta)
    {
        // cerr << d.first << " : " << d.second << '\n';
        if(prev != -1 && curr < R)
        {
            ans += d.first - prev;
        }
        curr += d.second;
        prev = d.first;
    }
    // cerr << '\n';

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

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