Submission #624193

#	Time	Username	Problem	Language	Result	Execution time	Memory
624193		MilosMilutinovic	Nekameleoni (COCI15_nekameleoni)	C++14	140 / 140	1212 ms	36480 KiB

nekameleoni

/**
 *    author:  wxhtzdy
 *    created: 07.08.2022 13:53:02
**/
#include <bits/stdc++.h>

using namespace std;

int k;

class segtree {
  public:
  struct node {
    // don't forget to set default value (used for leaves)
    // not necessarily neutral element!
    int ans = (k == 1 ? 1 : 1e9);
    vector<pair<int, int>> L;
    vector<pair<int, int>> R;
    long long mask = 0;
    void apply(int l, int r, int v) {
      L = {{v, l}};
      R = {{v, r}};
      mask = (1LL << v);
    }
  };
  node unite(const node &a, const node &b) const {
    node res;
    {     
      res.ans = min(a.ans, b.ans);
      res.mask = a.mask | b.mask;
      long long maskL = 0;
      long long maskR = b.mask;
      int j = (int) b.L.size() - 1;
      for (int i = 0; i < (int) a.R.size(); i++) {
        maskL = maskL | (1LL << a.R[i].first);
        while (j >= 0 && (maskL | (maskR ^ (1LL << b.L[j].first))) == (1LL << k) - 1) {
          maskR ^= (1LL << b.L[j].first);
          j -= 1;
        }
        if (j >= 0 && (maskL | maskR) == (1LL << k) - 1) {
          res.ans = min(res.ans, b.L[j].second - a.R[i].second + 1);
        }
      }
    }
    {
      res.L.clear();
      long long mask = 0;
      for (auto& p : a.L) {
        if (!(mask >> p.first & 1)) {
          mask |= (1LL << p.first);
          res.L.push_back(p);  
        }
      }
      for (auto& p : b.L) {
        if (!(mask >> p.first & 1)) {
          mask |= (1LL << p.first);
          res.L.push_back(p);  
        }
      }
    }
    {
      res.R.clear();
      long long mask = 0;
      for (auto& p : b.R) {
        if (!(mask >> p.first & 1)) {
          mask |= (1LL << p.first);
          res.R.push_back(p);  
        }
      }
      for (auto& p : a.R) {
        if (!(mask >> p.first & 1)) {
          mask |= (1LL << p.first);
          res.R.push_back(p);  
        }
      }
    }
    return res;
  }
  inline void push(int x, int l, int r) {
  }
  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }
  int n;
  vector<node> tree;
  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once
  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> k >> m;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    --a[i];
  }
  segtree st(a);
  while (m--) {
    int op;
    cin >> op;
    if (op == 1) {
      int p, v;
      cin >> p >> v;
      --p; --v;
      st.modify(p, p, v);
    } else {    
      int ans = st.get(0, n - 1).ans;
      cout << (ans == 1e9 ? -1 : ans) << '\n';
    }
  }                                                       
  return 0;
}

• 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