Submission #593638

#	Time	Username	Problem	Language	Result	Execution time	Memory
593638		AlesL0	Martian DNA (BOI18_dna)	C++17	100 / 100	404 ms	10880 KiB

dna

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e10;

vector <ll> T;
ll k = 1;

void build(vector <ll> a){
    ll n = a.size();
    while (k < n)k *= 2;
    T.resize(2*k);
    for (int i = 0; i < n; i++)T[i+k] = a[i];
    for (int i = n; i < k; i++)T[i+k] = INF;
    for (int i = k-1; i > 0; i--)T[i] = min(T[2*i], T[2*i+1]);
}

void reset(vector <ll> a){
    ll n = a.size();
    for (int i = 0; i < n; i++)T[i+k] = a[i];
    for (int i = n; i < k; i++)T[i+k] = INF;
    for (int i = k-1; i > 0; i--)T[i] = min(T[2*i], T[2*i+1]);
}

void update(ll x, ll v){
    x += k; T[x] += v; x >>= 1;
    for (; x; x >>= 1){
        T[x] = min(T[2*x], T[2*x+1]);
    }
}

int main(){
    ll n, K, r; cin >> n >> K >> r;
    vector <ll> v(n), aa(K, 0);
    for (int i = 0; i < n; i++)cin >> v[i];
    for (int i = 0; i < r; i++){
        ll a, b; cin >> a >> b;
        aa[a] = -b;
    }
    build(aa);
    ll s = 1, e = n+1, m, M = -1;
    while (e > s){
        m = (e+s)/2;
        for (int i = 0; i < m; i++)update(v[i], 1);
        for (int i = m; i < n; i++){
            if (T[1] >= 0){M = m; break;}
            update(v[i-m], -1); update(v[i], 1);
        }
        if (T[1] >= 0)M = m;
        if (M == m)e = m;
        else s = m+1;
        reset(aa);
    }
    if (M == -1)cout << "impossible";
    else cout << M;
}

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