oj.uz

Submission #653684

# Submission time Handle Problem Language Result Execution time Memory
653684 2022-10-27T17:02:41 Z PagodePaiva Martian DNA (BOI18_dna) C++14
0 / 100
 317 ms 16588 KB 
#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];
map <int, int> q;
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, v[i], true);
    }

    while(r <= n){
        if(seg.query()){
            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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 328 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2004 KB Output is correct
2 Correct 14 ms 1936 KB Output is correct
3 Correct 17 ms 1916 KB Output is correct
4 Correct 15 ms 2016 KB Output is correct
5 Correct 153 ms 7896 KB Output is correct
6 Correct 17 ms 2092 KB Output is correct
7 Correct 26 ms 2028 KB Output is correct
8 Incorrect 317 ms 16588 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 7896 KB Output is correct
2 Correct 174 ms 6360 KB Output is correct
3 Correct 143 ms 6380 KB Output is correct
4 Correct 13 ms 1992 KB Output is correct
5 Correct 146 ms 9292 KB Output is correct
6 Incorrect 292 ms 15308 KB Output isn't correct
7 Halted 0 ms 0 KB -