oj.uz

Submission #858875

# Submission time Handle Problem Language Result Execution time Memory
858875 2023-10-09T10:07:19 Z thanh913 Nekameleoni (COCI15_nekameleoni) C++14
140 / 140
 824 ms 38628 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22880 KB Output is correct
2 Correct 14 ms 22860 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 23132 KB Output is correct
2 Correct 35 ms 23196 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 25876 KB Output is correct
2 Correct 736 ms 34460 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 31424 KB Output is correct
2 Correct 765 ms 37316 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 29360 KB Output is correct
2 Correct 824 ms 35608 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 33276 KB Output is correct
2 Correct 783 ms 36196 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 32324 KB Output is correct
2 Correct 812 ms 36984 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 38628 KB Output is correct
2 Correct 814 ms 38416 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 38540 KB Output is correct
2 Correct 820 ms 38408 KB Output is correct