oj.uz

Submission #1015180

# Submission time Handle Problem Language Result Execution time Memory
1015180 2024-07-06T07:04:30 Z May27_th Nekameleoni (COCI15_nekameleoni) C++17
140 / 140
 1541 ms 55932 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2824 KB Output is correct
2 Correct 23 ms 2652 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3416 KB Output is correct
2 Correct 44 ms 3164 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 12116 KB Output is correct
2 Correct 1173 ms 38952 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 30800 KB Output is correct
2 Correct 1538 ms 52312 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 24020 KB Output is correct
2 Correct 1340 ms 45356 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 949 ms 36132 KB Output is correct
2 Correct 1322 ms 47700 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 34112 KB Output is correct
2 Correct 1541 ms 50448 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1270 ms 55892 KB Output is correct
2 Correct 1460 ms 55216 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1351 ms 55932 KB Output is correct
2 Correct 1336 ms 55008 KB Output is correct