Submission #263058

#	Time	Username	Problem	Language	Result	Execution time	Memory
263058		NONAME	Nekameleoni (COCI15_nekameleoni)	C++14	140 / 140	2830 ms	47096 KiB

nekameleoni

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 500;

int n, m, k;
int a[N];

struct tree {
    tree *L, *R;
    int val;
    vector <pair <ll, int> > pf, sf;

    tree () {
        val = 1e9;
        pf.clear();
        sf.clear();
    }

    pair <pair <vector <pair <ll, int> >, vector <pair <ll, int> > >, int> combine(tree *lft, tree *rgt) {
        vector <pair <ll, int> > res_pf, res_sf;
        int cur_val = 1e9;

        vector <pair <ll, int> > left, right;
        left = (lft -> pf);
        right = (rgt -> pf);
                   
        res_pf = left;
        for (int i = 0; i < int(right.size()); ++i)
            if ((res_pf.back().first | right[i].first) != res_pf.back().first)
                res_pf.push_back(make_pair(res_pf.back().first | right[i].first, right[i].second));

        left = (lft -> sf);
        right = (rgt -> sf);
        res_sf = right;
        for (int i = 0; i < int(left.size()); ++i)
            if ((res_sf.back().first | left[i].first) != res_sf.back().first)
                res_sf.push_back(make_pair(res_sf.back().first | left[i].first, left[i].second));

        left = (lft -> sf);
        right = (rgt -> pf);
        cur_val = min(lft -> val, rgt -> val);
        int p = int(right.size()) - 1;
        for (int i = 0; i < int(left.size()); ++i) {
            while (p >= 0 && (left[i].first | right[p].first) == (1ll << k) - 1)
                --p;

            if (p + 1 < int(right.size()) && (left[i].first | right[p + 1].first) == (1ll << k) - 1)
                cur_val = min(cur_val, right[p + 1].second - left[i].second + 1);
        }

        return make_pair(make_pair(res_pf, res_sf), cur_val);
    }
    
    void build(int l, int r) {
        if (l > r)
            return;

        if (l == r) {
            val = 1e9;
            if (k == 1)
                val = 1;
            pf.push_back(make_pair((1ll << a[l]), l));
            sf.push_back(make_pair((1ll << a[l]), l));
            return;
        }

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

        L = new tree();
        R = new tree();

        L -> build(l, md);
        R -> build(md + 1, r);
        
        auto cur = combine(L, R);

        pf = cur.first.first;
        sf = cur.first.second;
        val = cur.second;
    }

    void upd(int l, int r, int p, int v) {
        if (l == r) {
            val = 1e9;
            
            if (k == 1)
                val = 1;
            a[l] = v;
            
            pf[0] = sf[0] = make_pair((1ll << a[l]), l);
            return;
        }

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

        if (p <= md) L -> upd(l, md, p, v);
            else R -> upd(md + 1, r, p, v);

        auto cur = combine(L, R);

        pf = cur.first.first;
        sf = cur.first.second;
        val = cur.second;
    }

    /*void show(int l, int r) {
        if (l > r)
            return;

        cerr << l + 1 << " " << r + 1 << "\n";
        cerr << val << "\n";
        for (int i = 0; i < int(pf.size()); ++i)
            cerr << pf[i].first << " " << pf[i].second << "\n";
        cerr << "---\n";
        for (int i = 0; i < int(sf.size()); ++i)
            cerr << sf[i].first << " " << sf[i].second << "\n";
        cerr << "!--------------\n\n";

        if (l == r)
            return;

        int md = (l + r) >> 1;
        L -> show(l, md);
        R -> show(md + 1, r);
    }*/
};

int main() {  
    cin >> n >> k >> m;
    for (int i = 0; i < n; ++i)
        cin >> a[i], --a[i];

    tree t;
    t.build(0, n - 1);
    //t.show(0, n - 1);

    for (int i = 0; i < m; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int p, v;
            cin >> p >> v;
            --p; --v;
            t.upd(0, n - 1, p, v);
        } else cout << (t.val == 1e9 ? -1 : t.val) << "\n";
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14