#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;
const int offset = (1 << 17) + 7;
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) {
pref[p_sz ++] = x;
}
void add_suff(pair<long long, int> x) {
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
};
node t[offset << 1];
void modify(int p, long long v) {
p += offset;
t[p] = node(v);
for (int i = p / 2; i; i >>= 1) {
t[i] = t[i << 1] + t[i << 1 | 1];
}
}
int get_ans() {
return t[1].best == (int) 1e9 ? -1 : t[1].best;
}
} st;
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;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
208 ms |
414796 KB |
Output is correct |
| 2 |
Correct |
215 ms |
414884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
414868 KB |
Output is correct |
| 2 |
Correct |
252 ms |
414820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
251 ms |
414976 KB |
Output is correct |
| 2 |
Correct |
237 ms |
414884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
587 ms |
415408 KB |
Output is correct |
| 2 |
Correct |
1327 ms |
416116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
914 ms |
415776 KB |
Output is correct |
| 2 |
Correct |
1382 ms |
416496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1132 ms |
415864 KB |
Output is correct |
| 2 |
Correct |
1359 ms |
416324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1265 ms |
416012 KB |
Output is correct |
| 2 |
Correct |
1405 ms |
416324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1174 ms |
415968 KB |
Output is correct |
| 2 |
Correct |
1448 ms |
416452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1605 ms |
416356 KB |
Output is correct |
| 2 |
Correct |
1482 ms |
416488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1566 ms |
416304 KB |
Output is correct |
| 2 |
Correct |
1461 ms |
416524 KB |
Output is correct |
