Submission #399755

#	Time	Username	Problem	Language	Result	Execution time	Memory
399755		Sorting	Martian DNA (BOI18_dna)	C++17	100 / 100	40 ms	2704 KiB

dna

#include <bits/stdc++.h>

using namespace std;
template<typename T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<typename T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
typedef long long ll;
#define all(x) (x).begin(), (x).end()
int read_int();

const int N = 2e5 + 3;

int n, k, r, a[N];
int mn[N], cnt[N], cnt_ok;

void add(int x){
    ++cnt[x];
    if(cnt[x] == mn[x]) ++cnt_ok;
}

void rem(int x){
    if(cnt[x] == mn[x]) --cnt_ok;
    --cnt[x];
}

bool check(int mid){
    fill(cnt, cnt + k, 0);
    cnt_ok = k - r;
    for(int i = 0; i < mid; ++i)
        add(a[i]);

    if(cnt_ok == k) return true;

    for(int i = mid; i < n; ++i){
        add(a[i]);
        rem(a[i - mid]);
        if(cnt_ok == k) return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    n = read_int(), k = read_int(), r = read_int();
    for(int i = 0; i < n; ++i)
        a[i] = read_int();
    for(int i = 0; i < r; ++i){
        int b, q;
        b = read_int(), q = read_int();
        mn[b] = q;
    }

    int l = 1, r = n + 1;
    while(l != r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    if(l == n + 1) cout << "impossible\n";
    else cout << l << "\n";
}

int ptr = 0;
char buff[N];

void next_char(){ if(++ptr == N) fread(buff, 1, N, stdin), ptr = 0; }

int read_int(){
    int ret = 0;
    for(; buff[ptr] < '0' || buff[ptr] > '9'; next_char());
    for(; '0' <= buff[ptr] && buff[ptr] <= '9'; next_char())
        ret = 10 * ret + buff[ptr] - '0';
    return ret;
}

Compilation message (stderr)

dna.cpp: In function 'void next_char()':
dna.cpp:68:39: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   68 | void next_char(){ if(++ptr == N) fread(buff, 1, N, stdin), ptr = 0; }
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~

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