oj.uz

Submission #491187

# Submission time Handle Problem Language Result Execution time Memory
491187 2021-11-30T17:18:54 Z blue Lasers (NOI19_lasers) C++17
63 / 100
 292 ms 262148 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6840 KB Output is correct
2 Correct 14 ms 4808 KB Output is correct
3 Correct 19 ms 4936 KB Output is correct
4 Correct 50 ms 7184 KB Output is correct
5 Correct 29 ms 6076 KB Output is correct
6 Correct 66 ms 8572 KB Output is correct
7 Correct 3 ms 3532 KB Output is correct
8 Correct 70 ms 8916 KB Output is correct
9 Correct 28 ms 5444 KB Output is correct
10 Correct 55 ms 7388 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6840 KB Output is correct
2 Correct 14 ms 4808 KB Output is correct
3 Correct 19 ms 4936 KB Output is correct
4 Correct 50 ms 7184 KB Output is correct
5 Correct 29 ms 6076 KB Output is correct
6 Correct 66 ms 8572 KB Output is correct
7 Correct 3 ms 3532 KB Output is correct
8 Correct 70 ms 8916 KB Output is correct
9 Correct 28 ms 5444 KB Output is correct
10 Correct 55 ms 7388 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 286 ms 37056 KB Output is correct
22 Correct 35 ms 5204 KB Output is correct
23 Correct 20 ms 4736 KB Output is correct
24 Correct 81 ms 7248 KB Output is correct
25 Correct 287 ms 36932 KB Output is correct
26 Correct 65 ms 6400 KB Output is correct
27 Correct 30 ms 4964 KB Output is correct
28 Correct 275 ms 36972 KB Output is correct
29 Correct 292 ms 37132 KB Output is correct
30 Correct 62 ms 6332 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -