oj.uz

Submission #709480

# Submission time Handle Problem Language Result Execution time Memory
709480 2023-03-13T16:50:02 Z stevancv Martian DNA (BOI18_dna) C++14
100 / 100
 188 ms 143160 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9;
const int mod = 1e9 + 7;
deque<int> dq[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> b(m);
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        b[x] = y;
    }
    set<int> s;
    int dobri = 0;
    int ans = 1e6;
    for (int i = 0; i < n; i++) {
        if (b[a[i]] == 0) continue;
        dq[a[i]].push_back(i);
        if (dq[a[i]].size() > b[a[i]]) {
            s.erase(dq[a[i]].front());
            dq[a[i]].pop_front();
            s.insert(dq[a[i]].front());
        }
        else if (dq[a[i]].size() == b[a[i]]) {
            s.insert(dq[a[i]].front());
            dobri += 1;
        }
        if (dobri == k) smin(ans, i - *s.begin() + 1);
    }
    if (ans == 1e6) cout << "impossible" << en;
    else cout << ans << en;
    return 0;
}

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:33:29: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   33 |         if (dq[a[i]].size() > b[a[i]]) {
dna.cpp:38:34: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   38 |         else if (dq[a[i]].size() == b[a[i]]) {

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 134916 KB Output is correct
2 Correct 78 ms 134880 KB Output is correct
3 Correct 85 ms 134900 KB Output is correct
4 Correct 85 ms 134948 KB Output is correct
5 Correct 88 ms 134948 KB Output is correct
6 Correct 84 ms 135016 KB Output is correct
7 Correct 89 ms 134944 KB Output is correct
8 Correct 85 ms 134940 KB Output is correct
9 Correct 84 ms 134828 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 135072 KB Output is correct
2 Correct 87 ms 134984 KB Output is correct
3 Correct 80 ms 134948 KB Output is correct
4 Correct 77 ms 135000 KB Output is correct
5 Correct 79 ms 134976 KB Output is correct
6 Correct 86 ms 134972 KB Output is correct
7 Correct 81 ms 134864 KB Output is correct
8 Correct 80 ms 134860 KB Output is correct
9 Correct 78 ms 134824 KB Output is correct
10 Correct 77 ms 134852 KB Output is correct
11 Correct 81 ms 134856 KB Output is correct
12 Correct 78 ms 134880 KB Output is correct
13 Correct 81 ms 134836 KB Output is correct
14 Correct 78 ms 134860 KB Output is correct
15 Correct 77 ms 134904 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 136124 KB Output is correct
2 Correct 97 ms 135872 KB Output is correct
3 Correct 100 ms 136248 KB Output is correct
4 Correct 100 ms 136388 KB Output is correct
5 Correct 91 ms 137164 KB Output is correct
6 Correct 97 ms 136872 KB Output is correct
7 Correct 94 ms 136324 KB Output is correct
8 Correct 100 ms 137676 KB Output is correct
9 Correct 92 ms 136604 KB Output is correct
10 Correct 106 ms 136444 KB Output is correct
11 Correct 87 ms 134976 KB Output is correct
12 Correct 96 ms 134948 KB Output is correct
13 Correct 79 ms 134984 KB Output is correct
14 Correct 80 ms 134988 KB Output is correct
15 Correct 81 ms 134988 KB Output is correct
16 Correct 103 ms 134936 KB Output is correct
17 Correct 86 ms 134860 KB Output is correct
18 Correct 79 ms 134864 KB Output is correct
19 Correct 78 ms 134880 KB Output is correct
20 Correct 79 ms 134948 KB Output is correct
21 Correct 78 ms 134828 KB Output is correct
22 Correct 83 ms 134864 KB Output is correct
23 Correct 77 ms 134988 KB Output is correct
24 Correct 78 ms 134904 KB Output is correct
25 Correct 80 ms 134924 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 139716 KB Output is correct
2 Correct 174 ms 138872 KB Output is correct
3 Correct 119 ms 138188 KB Output is correct
4 Correct 100 ms 136012 KB Output is correct
5 Correct 129 ms 138184 KB Output is correct
6 Correct 159 ms 143160 KB Output is correct
7 Correct 129 ms 137056 KB Output is correct
8 Correct 145 ms 137676 KB Output is correct
9 Correct 102 ms 136488 KB Output is correct
10 Correct 99 ms 136268 KB Output is correct
11 Correct 98 ms 136152 KB Output is correct
12 Correct 105 ms 136340 KB Output is correct
13 Correct 97 ms 137080 KB Output is correct
14 Correct 100 ms 136924 KB Output is correct
15 Correct 99 ms 136228 KB Output is correct
16 Correct 101 ms 137776 KB Output is correct
17 Correct 93 ms 136652 KB Output is correct
18 Correct 110 ms 136364 KB Output is correct
19 Correct 84 ms 134976 KB Output is correct
20 Correct 88 ms 134860 KB Output is correct
21 Correct 78 ms 134988 KB Output is correct
22 Correct 77 ms 134988 KB Output is correct
23 Correct 77 ms 134860 KB Output is correct
24 Correct 86 ms 134896 KB Output is correct
25 Correct 79 ms 134860 KB Output is correct
26 Correct 79 ms 134924 KB Output is correct
27 Correct 78 ms 134944 KB Output is correct
28 Correct 77 ms 134904 KB Output is correct
29 Correct 79 ms 134920 KB Output is correct
30 Correct 79 ms 134924 KB Output is correct
31 Correct 76 ms 134832 KB Output is correct
32 Correct 78 ms 134896 KB Output is correct
33 Correct 76 ms 134860 KB Output is correct