Submission #485478

#	Time	Username	Problem	Language	Result	Execution time	Memory
485478		sam571128	Martian DNA (BOI18_dna)	C++17	100 / 100	38 ms	6724 KiB

dna

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e5+5, MOD = 1e9+7;
int val[N], cnt[N], arr[N];
int ans = 0;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int fastpow(int n, int p){
    int res = 1;
    while(p){
        if(p&1) res = res * n % MOD;
        n = n * n % MOD;
        p >>= 1;
    }
    return res;
}

int hsh(int x){
    if(cnt[x] <= 0) return 0;
    return cnt[x] * val[x];
}

bool check(int x){
    int tmp = ans;
    ans = ((ans-hsh(x))%MOD+MOD)%MOD;
    cnt[x]--;
    ans = ((ans+hsh(x))%MOD+MOD)%MOD;
    bool ok = (ans!=0);
    cnt[x]++;
    ans = tmp;
    return ok;
}

signed main(){
    fastio
    int n,k,R;
    cin >> n >> k >> R;
    for(int i = 0;i < n;i++){
        cin >> arr[i];
    }   

    for(int i = 0;i < R;i++){
        int x;
        cin >> x;
        val[x] = uniform_int_distribution<int>(0,1e9)(rng);
        cin >> cnt[x];
        ans += hsh(x);
    }

    int l = 0, r = -1, res = 1e18;
    while(l < n){
        while(r + 1 < n && check(arr[r+1])){
            ans = ((ans-hsh(arr[r+1]))%MOD+MOD)%MOD;
            cnt[arr[r+1]]--;
            ans = ((ans+hsh(arr[r+1]))%MOD+MOD)%MOD;
            r++;         
        }
        if(r+1 < n&&!check(arr[r+1])){
            res = min(res,r-l+2);
        }

        ans = ((ans-hsh(arr[l]))%MOD+MOD)%MOD;
        cnt[arr[l]]++;
        ans = ((ans+hsh(arr[l]))%MOD+MOD)%MOD;
        l++;
    }

    if(res==1e18) cout << "impossible\n";
    else cout << res << "\n";
}

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