Submission #648026

#	Time	Username	Problem	Language	Result	Execution time	Memory
648026		Shin	Nekameleoni (COCI15_nekameleoni)	C++14	70 / 140	1403 ms	524288 KiB

nekameleoni

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

long long target;
struct segment_tree {
  struct node {
    pair<long long, int> pref[50], suff[50];
    int best;
    int len;
    int p_sz, s_sz;
    node() {
      len = p_sz = s_sz = 0;
      best = (int) 1e9;
    }
    node(long long v) {
      len = p_sz = s_sz = 1;
      best = (v == target ? 1 : (int) 1e9);
      pref[0] = suff[0] = mp(v, 1);
    }
    void add_pref(pair<long long, int> x) {
      assert(p_sz <= 50);
      pref[p_sz ++] = x;
    }
    void add_suff(pair<long long, int> x) {
      assert(s_sz <= 50);
      suff[s_sz ++] = x;
    }
    #define new_bit(s1, s2) ((s1 | s2) != s1)
    friend node operator + (node &a, node &b) {
      node res;
      for (int i = 0; i < a.p_sz; i ++) {
        res.add_pref(a.pref[i]);
      }
      for (int i = 0; i < b.s_sz; i ++) {
        res.add_suff(b.suff[i]);
      }
      long long mask = a.pref[a.p_sz - 1].fi;
      for (int i = 0; i < b.p_sz; i ++) {
        if (!new_bit(mask, b.pref[i].fi)) {
          continue;
        }
        mask |= b.pref[i].fi;
        res.add_pref(mp(mask, a.len + b.pref[i].se));
      }
      mask = b.suff[b.s_sz - 1].fi;
      for (int i = 0; i < a.s_sz; i ++) {
        if (!new_bit(mask, a.suff[i].fi)) {
          continue;
        }
        mask |= a.suff[i].fi;
        res.add_suff(mp(mask, b.len + a.suff[i].se));
      }
      for (int i = a.s_sz - 1, j = 0; ~i; i --) {
        while (j < b.p_sz && (a.suff[i].fi | b.pref[j].fi) != target) {
          j ++;
        }
        if (j == b.p_sz || (a.suff[i].fi | b.pref[j].fi) != target) {
          break;
        }
        minimize(res.best, a.suff[i].se + b.pref[j].se);
      }
      minimize(res.best, min(a.best, b.best));
      res.len = a.len + b.len;
      return res;
    }
    #undef new_bit
  };

  vector<node> t;
  int n;

  segment_tree(int _n) : n(_n) {
    t.resize((n << 2) + 7);
  }

  void modify(int id, int l, int r, int p, long long v) {
    if (l > p || r < p) {
      return;
    }
    if (l == r) {
      t[id] = node(v);
    } else {
      int mid = (l + r) >> 1;
      modify(id << 1, l, mid, p, v);
      modify(id << 1 | 1, mid + 1, r, p, v);
      t[id] = t[id << 1] + t[id << 1 | 1];
    }
  }

  void out(int id) {
    for (int i = 0; i < t[id].s_sz; i ++) {
      cout << t[id].suff[i].fi << " " << t[id].suff[i].se << '\n';
    }
  }
  void modify(int p, long long v) {
    modify(1, 1, n, p, v);
  }

  int get_ans() {
    return t[1].best == (int) 1e9 ? -1 : t[1].best;
  }
};

const int N = 1e5 + 7;
int n, m, k, q;
int a[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k >> q;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i];
    a[i] --;
  }
  target = (1LL << k) - 1;
  segment_tree st(n);
  for (int i = 1; i <= n; i ++) {
    st.modify(i, 1LL << a[i]);
  }
  while (q --) {
    int t; cin >> t;
    if (t == 2) {
      cout << st.get_ans() << '\n';
    } else {
      int p, v; cin >> p >> v;
      v --;
      st.modify(p, 1LL << v);
    }
  }
  return 0;
}

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