oj.uz

Submission #253964

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

struct seg{
    ll vls;
    int 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;

        ll le = 0;

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

            if ((le | rt.vls) == ALL){
                while (ptr > 0 && (le & (1ll << 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 & (1ll << a[pos])))
            res.pref.PB(pos);

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

    return res;
}

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

        st[v].vls = (1ll << 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 = (1ll << 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 = (1ll << (k + 1)) - 2ll;

    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 36 ms 25976 KB Output is correct
2 Correct 24 ms 25856 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 26112 KB Output is correct
2 Correct 33 ms 26112 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 26240 KB Output is correct
2 Correct 45 ms 26208 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 28792 KB Output is correct
2 Correct 840 ms 36728 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 34300 KB Output is correct
2 Correct 966 ms 40568 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 32248 KB Output is correct
2 Correct 981 ms 39544 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 36024 KB Output is correct
2 Correct 961 ms 40260 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 35320 KB Output is correct
2 Correct 938 ms 41108 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1082 ms 41516 KB Output is correct
2 Correct 963 ms 42488 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1119 ms 41576 KB Output is correct
2 Correct 1014 ms 42268 KB Output is correct