oj.uz

Submission #579009

# Submission time Handle Problem Language Result Execution time Memory
579009 2022-06-18T09:47:00 Z ddy888 Martian DNA (BOI18_dna) C++17
0 / 100
 49 ms 5404 KB 
#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;

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

void remove(int i) {
    if (i == 0) return;
    if (!req[arr[i]]) return;
    --cnt[arr[i]];
    if (cnt[arr[i]] + 1 == req[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) {
        if ((int)bases.size() < r) add(i);
        if ((int)bases.size() == r) {
            while (l < i && check(l)) {
                remove(l);
                ++l;
            }
            ans = min(ans, i - l + 1);
        }
    }
    if (ans == 1e9) cout << "impossible";
    else cout << ans;

    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 5404 KB Output isn't correct
2 Halted 0 ms 0 KB -