oj.uz

Submission #932638

# Submission time Handle Problem Language Result Execution time Memory
932638 2024-02-24T01:30:13 Z LOLOLO Martian DNA (BOI18_dna) C++17
100 / 100
 429 ms 156500 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 10;
int a[N], nxt[N];
vector <int> pos[N];
deque <int> dq[N];

ll solve() {
    int n, k, num;
    cin >> n >> k >> num;

    map <int, int> mp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]];
    }

    int timer = 0;
    for (auto &x : mp)
        x.s = timer++;

    for (int i = 1; i <= n; i++) {
        a[i] = mp[a[i]];
        pos[a[i]].pb(i);
    }

    for (int i = 0; i < num; i++) {
        int b, q;
        cin >> b >> q;
        b = mp[b];
        for (int j = 0; j < sz(pos[b]); j++) {
            if (j + q - 1 < sz(pos[b])) {
                nxt[pos[b][j]] = pos[b][j + q - 1];
            } else {
                nxt[pos[b][j]] = n + 1;
            }
        }
    }

    int l = 0, r = n, m, ans = -1;
    while (l <= r) {
        m = (l + r) / 2;
        int mx = 0, cnt = 0;
        bool ch = 0;

        for (int i = 1; i <= n; i++) {
            if (nxt[i]) {
                dq[a[i]].pb(nxt[i]);
                if (sz(dq[a[i]]) == 1) {
                    cnt++;
                    mx = max(mx, nxt[i]);
                }
            }

            if (i > m && nxt[i - m]) {
                dq[a[i - m]].pop_front();
                if (sz(dq[a[i - m]])) {
                    mx = max(mx, dq[a[i - m]].front());
                } else {
                    cnt--;
                }
            }

            if (mx <= i && cnt == num) {
                ch = 1;
                break;
            }
        }

        for (int i = 1; i <= n; i++)
            if (sz(dq[a[i]]))
                dq[a[i]].clear();

        if (ch) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    if (ans == -1) {
        cout << "impossible\n";
        return 0;
    }

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
        //cout << solve() << '\n';
    }

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 140116 KB Output is correct
2 Correct 64 ms 140116 KB Output is correct
3 Correct 61 ms 140112 KB Output is correct
4 Correct 63 ms 140168 KB Output is correct
5 Correct 67 ms 140120 KB Output is correct
6 Correct 61 ms 140116 KB Output is correct
7 Correct 61 ms 139908 KB Output is correct
8 Correct 60 ms 140116 KB Output is correct
9 Correct 77 ms 140328 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 140116 KB Output is correct
2 Correct 71 ms 140120 KB Output is correct
3 Correct 62 ms 140200 KB Output is correct
4 Correct 63 ms 140444 KB Output is correct
5 Correct 65 ms 140228 KB Output is correct
6 Correct 68 ms 140184 KB Output is correct
7 Correct 70 ms 140028 KB Output is correct
8 Correct 61 ms 139880 KB Output is correct
9 Correct 63 ms 140112 KB Output is correct
10 Correct 67 ms 140380 KB Output is correct
11 Correct 62 ms 140112 KB Output is correct
12 Correct 65 ms 140116 KB Output is correct
13 Correct 63 ms 140116 KB Output is correct
14 Correct 59 ms 140120 KB Output is correct
15 Correct 61 ms 140120 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 142624 KB Output is correct
2 Correct 112 ms 142316 KB Output is correct
3 Correct 96 ms 142284 KB Output is correct
4 Correct 125 ms 142628 KB Output is correct
5 Correct 166 ms 147556 KB Output is correct
6 Correct 109 ms 143224 KB Output is correct
7 Correct 124 ms 142340 KB Output is correct
8 Correct 275 ms 156380 KB Output is correct
9 Correct 133 ms 142728 KB Output is correct
10 Correct 127 ms 142672 KB Output is correct
11 Correct 72 ms 140344 KB Output is correct
12 Correct 67 ms 140116 KB Output is correct
13 Correct 73 ms 140116 KB Output is correct
14 Correct 63 ms 140452 KB Output is correct
15 Correct 64 ms 140112 KB Output is correct
16 Correct 80 ms 140396 KB Output is correct
17 Correct 64 ms 140116 KB Output is correct
18 Correct 68 ms 139952 KB Output is correct
19 Correct 60 ms 140120 KB Output is correct
20 Correct 60 ms 140112 KB Output is correct
21 Correct 60 ms 140116 KB Output is correct
22 Correct 69 ms 140112 KB Output is correct
23 Correct 65 ms 139932 KB Output is correct
24 Correct 62 ms 140124 KB Output is correct
25 Correct 61 ms 140124 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 147544 KB Output is correct
2 Correct 241 ms 146000 KB Output is correct
3 Correct 225 ms 145996 KB Output is correct
4 Correct 86 ms 142168 KB Output is correct
5 Correct 333 ms 149076 KB Output is correct
6 Correct 429 ms 155420 KB Output is correct
7 Correct 180 ms 143288 KB Output is correct
8 Correct 246 ms 144172 KB Output is correct
9 Correct 107 ms 142628 KB Output is correct
10 Correct 112 ms 142280 KB Output is correct
11 Correct 100 ms 142744 KB Output is correct
12 Correct 110 ms 142624 KB Output is correct
13 Correct 165 ms 147288 KB Output is correct
14 Correct 109 ms 143120 KB Output is correct
15 Correct 118 ms 142144 KB Output is correct
16 Correct 291 ms 156500 KB Output is correct
17 Correct 146 ms 142932 KB Output is correct
18 Correct 134 ms 142696 KB Output is correct
19 Correct 70 ms 140116 KB Output is correct
20 Correct 71 ms 140184 KB Output is correct
21 Correct 64 ms 140216 KB Output is correct
22 Correct 62 ms 140376 KB Output is correct
23 Correct 69 ms 140120 KB Output is correct
24 Correct 80 ms 139936 KB Output is correct
25 Correct 61 ms 140116 KB Output is correct
26 Correct 68 ms 139900 KB Output is correct
27 Correct 60 ms 140112 KB Output is correct
28 Correct 64 ms 139888 KB Output is correct
29 Correct 61 ms 140116 KB Output is correct
30 Correct 65 ms 140116 KB Output is correct
31 Correct 70 ms 140112 KB Output is correct
32 Correct 61 ms 140116 KB Output is correct
33 Correct 67 ms 140116 KB Output is correct