Submission #441632

#	Time	Username	Problem	Language	Result	Execution time	Memory
441632		Haruto810198	Martian DNA (BOI18_dna)	C++17	100 / 100	43 ms	6724 KiB

dna

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define double long double
 
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
 
#define vi vector<int>
#define pii pair<int,int>
 
#define pb push_back
#define eb emplace_back
#define mkp make_pair
 
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
 
const int MAX = 200010;
 
int n, k, r;
 
int arr[MAX];
int cnt[MAX];
int req[MAX];
int sat;
 
int lptr, rptr;
 
int res;
 
signed main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin>>n>>k>>r;
 
    FOR(i, 1, n, 1){
        cin>>arr[i];
    }
 
    FOR(i, 1, r, 1){
        int type;
        cin>>type;
        cin>>req[type];
    }
 
    res = INF;
    lptr = 1, rptr = 0;
    sat = 0;
    int type;
 
    while(lptr <= n){
 
        while(sat < r){
            rptr++;
            if(rptr > n) break;
 
            type = arr[rptr];
            cnt[type]++;
            if(cnt[type] == req[type]){
                sat++;
            }
        }
 
        if(rptr > n) break;
 
        res = min(res, rptr - lptr + 1);
 
        //cerr<<"["<<lptr<<", "<<rptr<<"]"<<endl;
 
        type = arr[lptr];
        if(cnt[type] == req[type]){
            sat--;
        }
        cnt[type]--;
        lptr++;
 
    }
 
    if(res == INF){
        cout<<"impossible"<<'\n';
    }
    else{
        cout<<res<<'\n';
    }
 
    return 0;
 
}

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