Submission #1268461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268461		ducdev	Martian DNA (BOI18_dna)	C++17	100 / 100	36 ms	2628 KiB

dna

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX_N = 2e5;
const int MOD = 1e9 + 7;

int n, k, q;
int a[MAX_N + 5], req[MAX_N + 5], cnt[MAX_N + 5];

bool valid(int len) {
    for (int i = 0; i < k; i++) cnt[i] = 0;

    int cntGood = 0;
    for (int i = 1; i <= n; i++) {
        if (i > len) {
            if (cnt[a[i - len]] == req[a[i - len]]) cntGood--;
            cnt[a[i - len]]--;
        };
        cnt[a[i]]++;
        if (cnt[a[i]] == req[a[i]]) cntGood++;

        if (cntGood == q) return true;
    };

    return false;
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

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

    for (int i = 1; i <= q; i++) {
        int type;
        cin >> type;
        cin >> req[type];
    };

    int l = 1, r = n, res = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (valid(mid)) {
            res = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    };

    if (res == 0)
        cout << "impossible";
    else
        cout << res;
};

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen("MAIN.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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