Submission #987619

#	Time	Username	Problem	Language	Result	Execution time	Memory
987619		AlphaMale06	Martian DNA (BOI18_dna)	C++17	100 / 100	95 ms	24224 KiB

dna

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+3;

vector<int> pos[N];
int cnt[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k, m;
    cin >> n >> k >> m;
    int a[n];
    for(int i=0; i< n; i++){
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    int req[k];
    for(int i=0; i < k; i++){
        req[i]=0;
    }
    for(int i=0; i< m; i++){
        int x, y;
        cin >> x >> y;
        req[x]=y;
    }
    multiset<int> st;
    for(int i=0; i< k; i++){
        if(req[i]==cnt[i])st.insert(n+1);
    }
    int ans=n+1;
    for(int i=0; i < n; i++){
        int val = a[i];
        if(cnt[val]<req[val]){
            cnt[val]++;
            if(cnt[val]==req[val])st.insert(pos[val][0]);
        }
        else if(cnt[val]>=req[val] && req[val]!=0){
            st.erase(st.find(pos[val][cnt[val]-req[val]]));
            cnt[val]++;
            st.insert(pos[val][cnt[val]-req[val]]);
        }
        if(st.size()==k)ans=min(ans, i-(*st.begin())+1);
    }
    if(ans==n+1)cout << "impossible\n";
    else cout << ans << '\n';
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:46:21: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if(st.size()==k)ans=min(ans, i-(*st.begin())+1);
      |            ~~~~~~~~~^~~

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