Submission #1015180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015180		May27_th	Nekameleoni (COCI15_nekameleoni)	C++17	140 / 140	1541 ms	55932 KiB

nekameleoni

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define i128 __int128
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
int K;
struct CustomTree {
  struct Data {
    vector<pair<i64, int>> pref, suff;
    int ans;
    Data () : ans(1000000000) {
      pref.clear(); suff.clear();
    }
  };
  int N;
  vector<Data> st;
  CustomTree(int _N) : N(_N), st(_N * 4 + 4) {}
  Data combine(Data L, Data R) {
    Data res;
    res.ans = min(L.ans, R.ans);
    res.pref = L.pref;
    if (res.pref.size() == 0) res.pref = R.pref;
    else {
      for (auto [x, p] : R.pref) {
        i64 last = res.pref.back().first;
        i64 cur = (last | x);
        if ((last != cur && (cur & last) == last)) {
          res.pref.pb(mp(cur, p));
        }
      }
    }

    res.suff = R.suff;
    if (res.suff.size() == 0) res.suff = L.suff;
    else {
      for (auto [x, p] : L.suff) {
        i64 last = res.suff.back().first;
        i64 cur = (last | x);
        if ((last != cur && (cur & last) == last)) {
          res.suff.pb(mp(cur, p));
        }
      }
    }

    int j = 0;
    for (int i = (int)L.suff.size() - 1; i >= 0; i --) {
      while (j < (int)R.pref.size() && (R.pref[j].first | L.suff[i].first) != (1LL << K) - 1) j ++;
      if (j < (int)R.pref.size()) {
        if ((R.pref[j].first | L.suff[i].first) == (1LL << K) - 1) {
          res.ans = min(res.ans, R.pref[j].second - L.suff[i].second + 1);
        }
      }
    }

    return res;
  };
  void update(int id, int l, int r, int p, int x) {
    if (p < l || p > r) return;
    if (l == r) {
      st[id].pref = {mp((1LL << x), p)};
      st[id].suff = {mp((1LL << x), p)};
      st[id].ans = (K == 1 ? 1 : 1000000000);
      // cout << id << " " << K << " " << st[id].ans << "\n";
      // cout << id << " " << st[id].pref.back() << " " << st[id].suff.back() << "\n";
      return;
    }
    int mid = (l + r)/2;
    update(id * 2, l, mid, p, x);
    update(id * 2 + 1, mid + 1, r, p, x);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
  }
};
void Solve(void) {
  int N, M; cin >> N >> K >> M;
  CustomTree T(N + 4);
  for (int i = 1; i <= N; i ++) {
    int x; cin >> x; x --;
    T.update(1, 1, N, i, x);
  }
  while (M --) {
    int op; cin >> op;
    if (op == 1) {
      int p, x; cin >> p >> x; 
      x --;
      T.update(1, 1, N, p, x);
    } else {
      cout << (T.st[1].ans == 1000000000 ? -1 : T.st[1].ans) << "\n";
      // for (auto x : T.st[1].pref) cout << x << " "; cout << "\n";
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests;
  while (Tests --) {
    Solve();
  }
}

• 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