oj.uz

Submission #676782

# Submission time Handle Problem Language Result Execution time Memory
676782 2023-01-01T06:07:40 Z Cyanmond Martian DNA (BOI18_dna) C++17
0 / 100
 209 ms 31344 KB 
#include <bits/stdc++.h>

int main() {
    int N, K, R;
    std::cin >> N >> K >> R;
    std::vector<int> D(N);
    for (auto &e : D) {
        std::cin >> e;
    }

    std::vector<std::vector<int>> index_list(K);
    for (int i = 0; i < N; ++i) {
        index_list[D[i]].push_back(i);
    }

    std::vector<std::vector<std::pair<int, bool>>> events(N + 1);
    while (R--) {
        int B, Q;
        std::cin >> B >> Q;
        const auto &list = index_list[B];
        if ((int)list.size() < Q) {
            events[0].push_back({3 * N, true});
            break;
        }
        events[0].push_back({list[Q - 1], true});
        for (int i = 0; i < (int)list.size() - Q; ++i) {
            events[list[i] + 1].push_back({list[i + Q - 1], false});
            events[list[i] + 1].push_back({list[i + Q], true});
        }
        events[list[(int)list.size() - Q] + 1].push_back({3 * N, true});
    }

    std::multiset<int> mls;
    int answer = N;
    for (int i = 0; i < N; ++i) {
        for (const auto &[v, b] : events[i]) {
            if (b) {
                mls.insert(v);
            } else {
                mls.erase(mls.find(v));
            }
        }
        answer = std::min(answer, *mls.rbegin() - i + 1);
    }

    if (answer == N) {
        std::cout << "impossible" << std::endl;
    } else {
        std::cout << answer << std::endl;
    }
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 572 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 296 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9864 KB Output is correct
2 Correct 47 ms 10716 KB Output is correct
3 Correct 56 ms 12072 KB Output is correct
4 Correct 48 ms 10924 KB Output is correct
5 Correct 80 ms 11368 KB Output is correct
6 Incorrect 39 ms 7236 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 26236 KB Output is correct
2 Correct 209 ms 22508 KB Output is correct
3 Correct 100 ms 14324 KB Output is correct
4 Correct 57 ms 12500 KB Output is correct
5 Correct 69 ms 12580 KB Output is correct
6 Correct 208 ms 31344 KB Output is correct
7 Correct 109 ms 12592 KB Output is correct
8 Correct 128 ms 14536 KB Output is correct
9 Correct 43 ms 9892 KB Output is correct
10 Correct 47 ms 10692 KB Output is correct
11 Correct 57 ms 11932 KB Output is correct
12 Correct 49 ms 10880 KB Output is correct
13 Correct 72 ms 11424 KB Output is correct
14 Incorrect 30 ms 7244 KB Output isn't correct
15 Halted 0 ms 0 KB -