Submission #579014

#	Time	Username	Problem	Language	Result	Execution time	Memory
579014		ddy888	Martian DNA (BOI18_dna)	C++17	100 / 100	82 ms	9304 KiB

dna

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 200010, INF = 2e9;

int n, k, r;
int arr[MAXN];
int req[MAXN];
int cnt[MAXN];
set<int> bases;
int ans = INF;

void remove(int i) {
    if (!req[arr[i]]) return;
    --cnt[arr[i]];
    if (cnt[arr[i]] < req[arr[i]]) {
        if (*bases.lower_bound(arr[i]) == arr[i]) bases.erase(arr[i]);
    }
}

void add(int i) {
    if (!req[arr[i]]) return;
    ++cnt[arr[i]];
    if (cnt[arr[i]] >= req[arr[i]]) bases.insert(arr[i]);
}

bool check(int i) {
    if (!req[arr[i]]) return true;
    return (cnt[arr[i]] > req[arr[i]]);
}

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

    cin >> n >> k >> r;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    for (int i = 1; i <= r; ++i) {
        int x, y; cin >> x >> y;
        req[x] = y;
    }
    int l = 1;
    for (int i = 1; i <= n; ++i) {
        add(i);
        if ((int)bases.size() == r) {
            while (l < i && check(l)) {
                remove(l);
                ++l;
            }
            ans = min(ans, i - l + 1);
        }
    }
    if (ans == INF) cout << "impossible";
    else cout << ans;

    return 0;
}

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