Submission #653692

#	Time	Username	Problem	Language	Result	Execution time	Memory
653692		PagodePaiva	Martian DNA (BOI18_dna)	C++14	100 / 100	94 ms	5376 KiB

dna

#include<bits/stdc++.h>
#define int long long 
#define ms(v) memset(v, -1, sizeof v)
#define pi pair<int, int>
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(), x.end()
#define INF 1e15
#define mp make_pair
#define itn int
#define N 200010

using namespace std;

int n, k, r;
int v[N];
int q[N];
int qtd[N];

struct Seg{
    bool tree[4*N];

    bool join(int a, int b){
        if(a == false) return false;
        if(b == false) return false;
        return true;
    }

    void build(int node, int l, int r){
        if(l == r){
            tree[node] = false;
            return;
        }

        int mid = (l+r) >> 1;

        build(2*node, l, mid);
        build(2*node+1, mid+1, r);

        tree[node] = join(tree[2*node], tree[2*node+1]);

        return;
    }

    void update(int node, int l, int r, int pos, int val){
        if(l == r){
            tree[node] = val;
            return;
        }

        int mid = (l+r) >> 1;

        if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
        else update(2*node+1, mid+1, r, pos, val);

        tree[node] = join(tree[2*node], tree[2*node+1]);

        return;
    }

    bool query(){
        return tree[1];
    }
} seg;

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k >> r;

    for(int i = 1;i <= n;i++){
        cin >> v[i];
        v[i]++;
    }

    for(int i = 1;i <= r;i++){
        int a, b;
        cin >> a >> b;
        a++;
        q[a] = b;
    }

    int l = 1, r = 1;
    qtd[v[1]] = 1;
    int res = INF;

    seg.build(1, 1, k);

    for(int i = 1;i <= k;i++){
        if(qtd[i] >= q[i]) seg.update(1, 1, k, i, true);
    }

    while(r <= n){
        if(seg.query()){
            // cout << l << " " << r << "\n";
            // cout << qtd[1] << " " << qtd[2] << "\n";
            res = min(res, r-l+1);
            qtd[v[l]]--;
            seg.update(1, 1, k, v[l], (qtd[v[l]] >= q[v[l]] ? true : false));
            l++;

            if(l > r){
                r++;
                qtd[v[r]]++;
                seg.update(1, 1, k, v[r], (qtd[v[r]] >= q[v[r]] ? true : false));
            }
        }

        else{
            r++;
            qtd[v[r]]++;
            seg.update(1, 1, k, v[r], (qtd[v[r]] >= q[v[r]] ? true : false));
        }
    }

    if(res == INF) cout << "impossible\n";
    else cout << res << "\n";

    return 0;   
}

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