Submission #858875

#	Time	Username	Problem	Language	Result	Execution time	Memory
858875		thanh913	Nekameleoni (COCI15_nekameleoni)	C++14	140 / 140	824 ms	38628 KiB

nekameleoni

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

#define fi first
#define se second
#define ll long long

const int N = 1e5+5;

//-------------------------------
int n, q, lim, a[N];

struct SegmentTree {
    struct Node {
        int best;
        vector<int> pre, suf;

        Node() {}
        Node(int pos) {
            best = 1e9;
            pre.push_back(pos);
            suf.push_back(pos);
        }

        inline ll up(int x) {return (1LL << x);}

        ll calc(vector<int>& pos) {
            ll mask = 0;
            for (auto u : pos) mask |= up(a[u]);
            return mask;
        }

        void upd(Node& n1, Node& n2) {
            pre = n1.pre; suf = n2.suf;
            best = min(n1.best, n2.best);

            if (pre.size() < lim) {
                pre.reserve(lim);
                ll mask = calc(pre);
                for (int u : n2.pre) {
                    if ((mask | up(a[u])) != mask) {
                        mask |= up(a[u]);
                        pre.push_back(u);
                    }
                }
            }

            if (suf.size() < lim) {
                suf.reserve(lim);
                ll mask = calc(suf);
                for (auto u : n1.suf) {
                    if ((mask | up(a[u])) != mask) {
                        mask |= up(a[u]);
                        suf.push_back(u);
                    }
                }
            }

            vector<int> cnt(lim, 0);
            vector<int> tmp = n1.suf;
            reverse(tmp.begin(), tmp.end());
            tmp.insert(tmp.end(), n2.pre.begin(), n2.pre.end());

            int khac = 0, j = -1;
            for (int i = 0; i < tmp.size(); i++) {
                if (j < i) {
                    j = i; cnt[a[tmp[i]]]++;
                    khac = 1;
                }
                while (j < ((int)tmp.size()) - 1 && khac < lim) {
                    j++; cnt[a[tmp[j]]]++;
                    if (cnt[a[tmp[j]]] == 1) khac++;
                }
                if (khac != lim) break;
                best = min(best, tmp[j] - tmp[i] + 1);
                cnt[a[tmp[i]]]--;
                if (cnt[a[tmp[i]]] == 0) khac--;
            }

            pre.shrink_to_fit();
            suf.shrink_to_fit();
        }
    };

    Node seg[N*4];
    void build(int l = 1, int r = n, int id = 1) {
        if (l == r) {
            seg[id] = Node(l);
            return;
        }
        int mid = (l+r) / 2;
        build(l, mid, id*2);
        build(mid+1, r, id*2 + 1);
        seg[id].upd(seg[id*2], seg[id*2 + 1]);
    }

    void update(int pos, int l = 1, int r = n, int id = 1) {
        if (l > pos || r < pos) return;
        if (l == r) {
            seg[id] = Node(l);
            return;
        }
        int mid = (l+r) / 2;
        update(pos, l, mid, id*2);
        update(pos, mid+1, r, id*2 + 1);
        seg[id].upd(seg[id*2], seg[id*2 + 1]);
    }

    int get() {return (seg[1].best == 1e9 ? -1 : seg[1].best);}
} tree;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> lim >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; a[i]--;
    }
    tree.build();
    while (q--) {
        int qr; cin >> qr;
        if (qr == 1) {
            int pos, val; cin >> pos >> val;
            a[pos] = val-1;
            tree.update(pos);
        }
        else {
            cout << tree.get() << '\n';
        }
    }
}

Compilation message (stderr)

nekameleoni.cpp: In member function 'void SegmentTree::Node::upd(SegmentTree::Node&, SegmentTree::Node&)':
nekameleoni.cpp:37:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |             if (pre.size() < lim) {
      |                 ~~~~~~~~~~~^~~~~
nekameleoni.cpp:48:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |             if (suf.size() < lim) {
      |                 ~~~~~~~~~~~^~~~~
nekameleoni.cpp:65:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for (int i = 0; i < tmp.size(); i++) {
      |                             ~~^~~~~~~~~~~~

• 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