Submission #1111273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111273		tuannm	Martian DNA (BOI18_dna)	C++17	100 / 100	23 ms	2816 KiB

dna

#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 2e5 + 1;
const string NAME = "";
int n, k, r, cnt[N], a[N], needed[N];

void inp(){
    cin >> n >> k >> r;

    for(int i = 1; i <= n; ++i)
        cin >> a[i], needed[a[i]] = n + 1;

    for(int i = 1; i <= r; ++i){
        int b, q;
        cin >> b >> q;

        needed[b] = q;
    }
}

void solve(){
    int j = 0, cntFulfill = 0, ans = n + 1;
    for(int i = 1; i <= n; ++i){
        while(j < n && cntFulfill < r){
            ++j;
            ++cnt[a[j]];
            cntFulfill += (cnt[a[j]] == needed[a[j]]);
        }

        if(cntFulfill == r)
            ans = min(ans, j - i + 1);

        cntFulfill -= (cnt[a[i]] == needed[a[i]]);
        --cnt[a[i]];
    }

    if(ans == n + 1)
        return (void) (cout << "impossible");
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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