Submission #643425

#	Time	Username	Problem	Language	Result	Execution time	Memory
643425		devariaota	Martian DNA (BOI18_dna)	C++17	100 / 100	31 ms	2636 KiB

dna

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll mod=1e9+7;
const ll maxn=2e5+5;
const int INF=1e9;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define endl '\n'
int n, k, r, arr[maxn], cnt[maxn], hrs[maxn], x, y, ans=INF, ls=1, tot;
bool use[maxn];
int main() {
    ok
    cin >> n >> k >> r;
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }
    for(int i=1; i<=r; i++) {
        cin >> x >> y;
        hrs[x]=y;
    }
    for(int i=1; i<=n; i++) {
        while(tot<r && ls<=n) {
            cnt[arr[ls]]++;
            if(!use[arr[ls]] && cnt[arr[ls]]>=hrs[arr[ls]] && hrs[arr[ls]]) {
                tot++;
                use[arr[ls]]=1;
            }
            ls++;
        }
        if(tot==r) {
            ans=min(ans, ls-i);
        }
        cnt[arr[i]]--;
        if(use[arr[i]] && cnt[arr[i]]<hrs[arr[i]]) {
            tot--;
            use[arr[i]]=0;
        }
    }
    if(ans==INF) cout << "impossible";
    else cout << ans;
}

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