oj.uz

Submission #253954

# Submission time Handle Problem Language Result Execution time Memory
253954 2020-07-29T07:31:29 Z VEGAnn Nekameleoni (COCI15_nekameleoni) C++14
14 / 140
 732 ms 37752 KB 
#include <bits/stdc++.h>
#define PB push_back
#define i2 array<int,2>
#define sz(x) ((int)x.size())
using namespace std;
const int N = 100100;
const int oo = 2e9;
int n, k, ALL, a[N];

struct seg{
    int vls, ans;
    vector<int> pref, suf;

    seg(): vls(0), ans(oo), pref(0), suf(0) {}

    void clear(){
        suf.clear();
        pref.clear();
        ans = oo;
        vls = 0;
    }
};

seg st[4 * N];

seg combine(seg &lf, seg &rt){
    seg res;

    res.clear();

    res.ans = min(lf.ans, rt.ans);

    res.vls = (lf.vls | rt.vls);

    if (res.vls == ALL){
        // recalc answer

        int ptr = sz(rt.pref) - 1;

        int le = 0;

        for (int pos : lf.suf){
            le |= (1 << a[pos]);

            if ((le | rt.vls) == ALL){
                while (ptr > 0 && (le & (1 << a[rt.pref[ptr]]))){
                    ptr--;
                }

                res.ans = min(res.ans, rt.pref[ptr] - pos + 1);
            }
        }
    }

    res.pref = lf.pref;
    res.suf = rt.suf;

    for (int pos : rt.pref)
        if (!(lf.vls & (1 << a[pos])))
            res.pref.PB(pos);

    for (int pos : lf.suf)
        if (!(rt.vls & (1 << a[pos])))
            res.suf.PB(pos);

    assert(__builtin_popcount(res.vls) == sz(res.pref));
    assert(__builtin_popcount(res.vls) == sz(res.suf));

    return res;
}

void build(int v, int l, int r){
    if (l == r){
        st[v].clear();

        st[v].vls = (1 << a[l]);

        st[v].pref.PB(l);
        st[v].suf.PB(l);

        return;
    }

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

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    st[v] = combine(st[v + v], st[v + v + 1]);
}

void update(int v, int l, int r, int ps){
    if (l == r){
        st[v].clear();

        st[v].vls = (1 << a[l]);

        st[v].pref.PB(l);
        st[v].suf.PB(l);

        return;
    }

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

    if (ps <= md)
        update(v + v, l, md, ps);
    else update(v + v + 1, md + 1, r, ps);

    st[v] = combine(st[v + v], st[v + v + 1]);
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    int qq;

    cin >> n >> k >> qq;

    ALL = (1 << (k + 1)) - 2;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    build(1, 0, n - 1);

    for (; qq; qq--){
        int tp; cin >> tp;

        if (tp == 1){
            int ps, vl; cin >> ps >> vl;
            ps--;

            a[ps] = vl;

            update(1, 0, n - 1, ps);
        } else {
            if (k == 1)
                cout << "1\n";
            else cout << (st[1].ans == oo ? -1 : st[1].ans) << '\n';
        }
    }

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 22784 KB Output is correct
2 Correct 23 ms 22784 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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