Submission #932638

#	Time	Username	Problem	Language	Result	Execution time	Memory
932638		LOLOLO	Martian DNA (BOI18_dna)	C++17	100 / 100	429 ms	156500 KiB

dna

#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 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32