// source problem :
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
f = (f < s ? f : s);
}
int k;
const int inf = 1e18;
struct info
{
vector<int> pre, suf, p, s;
int ans;
info()
{
ans = 0;
}
info(int val, int pos)
{
p.push_back(pos);
s.push_back(pos);
pre.push_back(val);
suf.push_back(val);
ans = (k == 1 ? 1 : inf);
}
};
info operator+(info a, info b)
{
if (!a.ans) return b;
if (!b.ans) return a;
info res;
res.ans = min(a.ans, b.ans);
res.pre = a.pre;
res.p = a.p;
for (int i = 0; i < b.pre.size(); i++)
{
int x = b.pre[i] | res.pre.back();
if (x != res.pre.back())
{
res.pre.push_back(x);
res.p.push_back(b.p[i]);
}
}
res.suf = b.suf;
res.s = b.s;
for (int i = 0; i < a.suf.size(); i++)
{
int x = a.suf[i] | res.suf.back();
if (x != res.suf.back())
{
res.suf.push_back(x);
res.s.push_back(a.s[i]);
}
}
int i = a.suf.size() - 1;
for (int j = 0; j < b.pre.size(); j++)
{
while (i >= 0 && (b.pre[j] | a.suf[i]) == MASK(k) - 1) i--;
if (i != a.suf.size() - 1)
{
ckmin(res.ans, b.p[j] - a.s[i + 1] + 1);
}
}
return res;
}
vector<int> a;
info st[1 << 18];
void build(int id = 1, int l = 1, int r = 1 << 17)
{
if (l == r)
{
if (l <= a.size()) st[id] = info(MASK(a[l - 1]), l);
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void update(int pos, int val, int id = 1, int l = 1, int r = 1 << 17)
{
if (pos < l || pos > r) return;
if (l == r)
{
st[id] = info(val, pos);
return;
}
int mid = (l + r) >> 1;
update(pos, val, id << 1, l, mid);
update(pos, val, id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> k >> q;
a.resize(n);
for (int &i : a) cin >> i, i--;
build();
while (q--)
{
int t;
cin >> t;
if (t == 2)
{
int x = st[1].ans;
cout << (x > n ? -1LL : x) << '\n';
}
else
{
int p, x;
cin >> p >> x;
x--;
update(p, MASK(x));
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |