#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
21972 KB |
Output is correct |
| 2 |
Correct |
29 ms |
21972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
27604 KB |
Output is correct |
| 2 |
Correct |
44 ms |
27592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
32004 KB |
Output is correct |
| 2 |
Correct |
64 ms |
31956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
416 ms |
130072 KB |
Output is correct |
| 2 |
Correct |
1257 ms |
447212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
885 ms |
345348 KB |
Output is correct |
| 2 |
Runtime error |
234 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
892 ms |
263536 KB |
Output is correct |
| 2 |
Correct |
1403 ms |
516980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1188 ms |
415496 KB |
Output is correct |
| 2 |
Runtime error |
227 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1178 ms |
384444 KB |
Output is correct |
| 2 |
Runtime error |
227 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
232 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
238 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
