oj.uz

Submission #752738

# Submission time Handle Problem Language Result Execution time Memory
752738 2023-06-03T14:21:50 Z benjaminkleyn Painting Walls (APIO20_paint) C++17
28 / 100
 232 ms 524288 KB 
#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
typedef bitset<50000> mask;

mask v[100000];
int lg[100001];

bool query(int l, int r, vector<vector<mask>> &raq)
{
    int t = lg[r - l + 1];
    return (raq[t][l] & raq[t][r - (1 << t) + 1]).count() > 0;
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
    lg[1] = 0;
    for (int x = 2; x <= N; x++)
        lg[x] = 1 + lg[x/2];
    for (int i = 0; i < M; i++)
        for (int c : B[i])
            v[c][i] = 1;

    mask ones;
    for (int i = 0; i < M; i++) ones[i] = 1;

    vector<vector<mask>> raq(20, vector<mask>(N));
    for (int i = 0; i < N; i++)
        raq[0][i] = ((v[C[i]] >> (i % M)) | (v[C[i]] << ((100000 * M - i) % M))) & ones;

    for (int t = 1; (1 << t) <= N; t++)
        for (int i = 0; i + (1 << t) - 1 < N; i++)
            raq[t][i] = raq[t-1][i] & raq[t-1][i + (1 << (t-1))];

    int ans = 0;
    for (int i = 0, j; i < N; i = j)
    {
        mask cur = raq[0][i];
        j = i + 1;
        for (int t = lg[N]; t >= 0; t--)
            if (j + (1 << t) - 1 < N && (cur & raq[t][j]).count() > 0)
            {
                cur &= raq[t][j];
                j += (1 << t);
            }

        j = min(j, i + M);
        if (!query(j-M, j-1, raq))
            return -1;
        ans++;
    }
    return ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 45 ms 64544 KB Output is correct
8 Correct 54 ms 64524 KB Output is correct
9 Correct 44 ms 64640 KB Output is correct
10 Correct 37 ms 64572 KB Output is correct
11 Correct 37 ms 64588 KB Output is correct
12 Correct 38 ms 64648 KB Output is correct
13 Correct 40 ms 67544 KB Output is correct
14 Correct 40 ms 67532 KB Output is correct
15 Correct 41 ms 67724 KB Output is correct
16 Correct 42 ms 67636 KB Output is correct
17 Correct 42 ms 67532 KB Output is correct
18 Correct 43 ms 67540 KB Output is correct
19 Correct 44 ms 69744 KB Output is correct
20 Correct 47 ms 69704 KB Output is correct
21 Correct 44 ms 69708 KB Output is correct
22 Correct 194 ms 466496 KB Output is correct
23 Correct 205 ms 466628 KB Output is correct
24 Correct 196 ms 466596 KB Output is correct
25 Runtime error 232 ms 524288 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 45 ms 64544 KB Output is correct
8 Correct 54 ms 64524 KB Output is correct
9 Correct 44 ms 64640 KB Output is correct
10 Correct 37 ms 64572 KB Output is correct
11 Correct 37 ms 64588 KB Output is correct
12 Correct 38 ms 64648 KB Output is correct
13 Correct 40 ms 67544 KB Output is correct
14 Correct 40 ms 67532 KB Output is correct
15 Correct 41 ms 67724 KB Output is correct
16 Correct 42 ms 67636 KB Output is correct
17 Correct 42 ms 67532 KB Output is correct
18 Correct 43 ms 67540 KB Output is correct
19 Correct 44 ms 69744 KB Output is correct
20 Correct 47 ms 69704 KB Output is correct
21 Correct 44 ms 69708 KB Output is correct
22 Correct 1 ms 1364 KB Output is correct
23 Correct 1 ms 980 KB Output is correct
24 Correct 1 ms 480 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 0 ms 596 KB Output is correct
27 Correct 25 ms 36664 KB Output is correct
28 Correct 26 ms 42668 KB Output is correct
29 Correct 20 ms 33564 KB Output is correct
30 Correct 29 ms 44628 KB Output is correct
31 Correct 37 ms 58060 KB Output is correct
32 Correct 33 ms 48204 KB Output is correct
33 Correct 35 ms 55764 KB Output is correct
34 Correct 36 ms 59172 KB Output is correct
35 Correct 24 ms 39252 KB Output is correct
36 Correct 31 ms 50900 KB Output is correct
37 Correct 31 ms 45396 KB Output is correct
38 Correct 27 ms 44244 KB Output is correct
39 Correct 30 ms 40432 KB Output is correct
40 Correct 28 ms 45372 KB Output is correct
41 Correct 27 ms 41428 KB Output is correct
42 Correct 36 ms 58800 KB Output is correct
43 Correct 28 ms 42688 KB Output is correct
44 Correct 45 ms 64528 KB Output is correct
45 Correct 41 ms 64724 KB Output is correct
46 Correct 43 ms 64564 KB Output is correct
47 Correct 39 ms 64624 KB Output is correct
48 Correct 40 ms 64564 KB Output is correct
49 Correct 40 ms 64624 KB Output is correct
50 Correct 43 ms 67556 KB Output is correct
51 Correct 50 ms 67504 KB Output is correct
52 Correct 53 ms 67620 KB Output is correct
53 Correct 46 ms 67524 KB Output is correct
54 Correct 44 ms 67532 KB Output is correct
55 Correct 52 ms 67568 KB Output is correct
56 Correct 45 ms 69716 KB Output is correct
57 Correct 41 ms 65912 KB Output is correct
58 Correct 45 ms 69716 KB Output is correct
59 Correct 43 ms 65868 KB Output is correct
60 Correct 48 ms 69732 KB Output is correct
61 Correct 40 ms 65860 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 45 ms 64544 KB Output is correct
10 Correct 54 ms 64524 KB Output is correct
11 Correct 44 ms 64640 KB Output is correct
12 Correct 37 ms 64572 KB Output is correct
13 Correct 37 ms 64588 KB Output is correct
14 Correct 38 ms 64648 KB Output is correct
15 Correct 40 ms 67544 KB Output is correct
16 Correct 40 ms 67532 KB Output is correct
17 Correct 41 ms 67724 KB Output is correct
18 Correct 42 ms 67636 KB Output is correct
19 Correct 42 ms 67532 KB Output is correct
20 Correct 43 ms 67540 KB Output is correct
21 Correct 44 ms 69744 KB Output is correct
22 Correct 47 ms 69704 KB Output is correct
23 Correct 44 ms 69708 KB Output is correct
24 Correct 194 ms 466496 KB Output is correct
25 Correct 205 ms 466628 KB Output is correct
26 Correct 196 ms 466596 KB Output is correct
27 Correct 1 ms 480 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 0 ms 596 KB Output is correct
30 Correct 25 ms 36664 KB Output is correct
31 Correct 26 ms 42668 KB Output is correct
32 Correct 20 ms 33564 KB Output is correct
33 Correct 29 ms 44628 KB Output is correct
34 Correct 37 ms 58060 KB Output is correct
35 Correct 33 ms 48204 KB Output is correct
36 Correct 35 ms 55764 KB Output is correct
37 Correct 36 ms 59172 KB Output is correct
38 Correct 24 ms 39252 KB Output is correct
39 Correct 31 ms 50900 KB Output is correct
40 Correct 31 ms 45396 KB Output is correct
41 Correct 27 ms 44244 KB Output is correct
42 Correct 30 ms 40432 KB Output is correct
43 Correct 28 ms 45372 KB Output is correct
44 Correct 27 ms 41428 KB Output is correct
45 Correct 36 ms 58800 KB Output is correct
46 Correct 28 ms 42688 KB Output is correct
47 Correct 45 ms 64528 KB Output is correct
48 Correct 41 ms 64724 KB Output is correct
49 Correct 43 ms 64564 KB Output is correct
50 Correct 39 ms 64624 KB Output is correct
51 Correct 40 ms 64564 KB Output is correct
52 Correct 40 ms 64624 KB Output is correct
53 Correct 43 ms 67556 KB Output is correct
54 Correct 50 ms 67504 KB Output is correct
55 Correct 53 ms 67620 KB Output is correct
56 Correct 46 ms 67524 KB Output is correct
57 Correct 44 ms 67532 KB Output is correct
58 Correct 52 ms 67568 KB Output is correct
59 Correct 45 ms 69716 KB Output is correct
60 Correct 41 ms 65912 KB Output is correct
61 Correct 45 ms 69716 KB Output is correct
62 Correct 43 ms 65868 KB Output is correct
63 Correct 48 ms 69732 KB Output is correct
64 Correct 40 ms 65860 KB Output is correct
65 Correct 20 ms 32880 KB Output is correct
66 Correct 39 ms 61692 KB Output is correct
67 Correct 39 ms 63180 KB Output is correct
68 Correct 42 ms 64268 KB Output is correct
69 Correct 38 ms 58060 KB Output is correct
70 Correct 36 ms 58680 KB Output is correct
71 Correct 42 ms 56824 KB Output is correct
72 Correct 40 ms 52684 KB Output is correct
73 Correct 35 ms 51744 KB Output is correct
74 Correct 31 ms 45908 KB Output is correct
75 Correct 32 ms 46036 KB Output is correct
76 Correct 121 ms 262188 KB Output is correct
77 Correct 152 ms 316948 KB Output is correct
78 Correct 151 ms 347212 KB Output is correct
79 Correct 43 ms 64652 KB Output is correct
80 Correct 41 ms 64580 KB Output is correct
81 Correct 40 ms 64608 KB Output is correct
82 Correct 39 ms 64628 KB Output is correct
83 Correct 41 ms 64588 KB Output is correct
84 Correct 42 ms 67584 KB Output is correct
85 Correct 44 ms 67636 KB Output is correct
86 Correct 48 ms 67668 KB Output is correct
87 Correct 43 ms 67668 KB Output is correct
88 Correct 44 ms 67676 KB Output is correct
89 Correct 43 ms 67608 KB Output is correct
90 Correct 181 ms 383696 KB Output is correct
91 Correct 186 ms 383032 KB Output is correct
92 Correct 169 ms 384320 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 45 ms 64544 KB Output is correct
10 Correct 54 ms 64524 KB Output is correct
11 Correct 44 ms 64640 KB Output is correct
12 Correct 37 ms 64572 KB Output is correct
13 Correct 37 ms 64588 KB Output is correct
14 Correct 38 ms 64648 KB Output is correct
15 Correct 40 ms 67544 KB Output is correct
16 Correct 40 ms 67532 KB Output is correct
17 Correct 41 ms 67724 KB Output is correct
18 Correct 42 ms 67636 KB Output is correct
19 Correct 42 ms 67532 KB Output is correct
20 Correct 43 ms 67540 KB Output is correct
21 Correct 44 ms 69744 KB Output is correct
22 Correct 47 ms 69704 KB Output is correct
23 Correct 44 ms 69708 KB Output is correct
24 Correct 194 ms 466496 KB Output is correct
25 Correct 205 ms 466628 KB Output is correct
26 Correct 196 ms 466596 KB Output is correct
27 Runtime error 232 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 45 ms 64544 KB Output is correct
10 Correct 54 ms 64524 KB Output is correct
11 Correct 44 ms 64640 KB Output is correct
12 Correct 37 ms 64572 KB Output is correct
13 Correct 37 ms 64588 KB Output is correct
14 Correct 38 ms 64648 KB Output is correct
15 Correct 40 ms 67544 KB Output is correct
16 Correct 40 ms 67532 KB Output is correct
17 Correct 41 ms 67724 KB Output is correct
18 Correct 42 ms 67636 KB Output is correct
19 Correct 42 ms 67532 KB Output is correct
20 Correct 43 ms 67540 KB Output is correct
21 Correct 44 ms 69744 KB Output is correct
22 Correct 47 ms 69704 KB Output is correct
23 Correct 44 ms 69708 KB Output is correct
24 Correct 194 ms 466496 KB Output is correct
25 Correct 205 ms 466628 KB Output is correct
26 Correct 196 ms 466596 KB Output is correct
27 Runtime error 232 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -