oj.uz

Submission #858880

# Submission time Handle Problem Language Result Execution time Memory
858880 2023-10-09T10:34:27 Z thanh913 Nekameleoni (COCI15_nekameleoni) C++14
140 / 140
 697 ms 38736 KB 
//time/mem test
#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) {
                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) {
                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--;
            }
        }
    };
 
    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:38:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |             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:64:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for (int i = 0; i < tmp.size(); i++) {
      |                             ~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22872 KB Output is correct
2 Correct 11 ms 22616 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22872 KB Output is correct
2 Correct 19 ms 22876 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23132 KB Output is correct
2 Correct 28 ms 23172 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 26204 KB Output is correct
2 Correct 586 ms 33708 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 31316 KB Output is correct
2 Correct 623 ms 37516 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 29268 KB Output is correct
2 Correct 642 ms 35416 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 33284 KB Output is correct
2 Correct 652 ms 36212 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 32408 KB Output is correct
2 Correct 675 ms 37560 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 38736 KB Output is correct
2 Correct 697 ms 38184 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 38520 KB Output is correct
2 Correct 669 ms 38220 KB Output is correct