Submission #862051

#	Time	Username	Problem	Language	Result	Execution time	Memory
862051		KK_1729	Martian DNA (BOI18_dna)	C++17	100 / 100	54 ms	18128 KiB

dna

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}
void solve(){
    int n, k, r; cin >> n >> k >> r;

    vector<int> d(n);
    FOR(i,0,n) cin >> d[i];

    vector<vector<int>> o(k);
    FOR(i,0,n) o[d[i]].pb(i);

    vector<int> e(k+1);
    FOR(i,0,r){
        int x, y; cin >> x >> y;
        e[x] = y;
    }



    vector<int> start(n);
    vector<int> end(n);
    vector<int> prev(n);
    vector<int> next(n);
    FOR(i,0,k){
        int h = o[i].size();
        if (e[i] == 0) continue; 
        int l = 0; int j = e[i]-1;
        while (j < h){
            start[o[i][l]] = 1;
            end[o[i][j]] = 1;
            prev[o[i][j]] = o[i][l];
            next[o[i][l]] = o[i][j];
            l++;
            j++;
        }
    }

    // printVector(start);
    // printVector(end);
    int first = 0; int second = n;
    int count = 0;
    int answer = n+1;
    while (first <= second){
        int mid = (first+second+1)/2;
        
        int l = 0; int j = mid-1;
        bool can = false;
        // vector<int> s(k), l(k);
        vector<int> current(k);
        int active = 0;
        FOR(i,l,j+1){
            if (end[i]){
                if (prev[i] >= l){
                    current[d[i]]++;
                    if (current[d[i]] == 1) active++;
                }
            }
            
            if (active >= r){
                l = mid;
                can = true;
            }
        }

        while (j < n){
            if (start[l] && next[l] <= j){
                current[d[l]]--;
                if (current[d[l]] == 0) active--;
            }
            l++;
            j++;
            if (end[j] && prev[j] >= l){
                current[d[j]]++;
                if (current[d[j]] == 1) active++;
            }
            if (active >= r) can = true;
        }
        // cout << mid << can << endl;
        if (can){
            second = mid;
            answer = min(answer, mid);
        }else{
            first = mid;
        }
        if (second-first <= 1){
            count++;
            if (count > 2){
                first = second;
            }
        }
        if (first == second) break;
        // cout << first << second << endl;
        // if ()break;
    }

    if (answer > n) cout << "impossible" << endl;
    else cout << answer << endl;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int t = 1;
    while (t--) solve();
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32