#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep2(i, j, n) for (LL i = j; i <= n; ++i)
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define boost cin.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 1e5 + 100;
const int INF = 1e9;
const int pod = (1 << 17);
int n, k, m;
int d[N];
int a, b, e;
LL full;
struct gao {
int ans, sum;
vector <pair<LL, int>> pref, suf;
gao() {}
gao(LL x) {
if (x == -1) {
ans = INF;
sum = 0;
pref = suf = {};
}
else {
ans = ((1LL << x) == full ? 1 : INF);
sum = 1;
pref = suf = {{1LL << x, 1}};
}
}
};
gao t[2 * pod], c;
int p, s, s2;
gao merge(const gao& a, const gao& b) {
c.ans = min(a.ans, b.ans);
c.pref.clear();
c.suf.clear();
c.sum = a.sum + b.sum;
p = ss(a.suf);
s = a.sum;
s2 = 0;
rep(i, 0, ss(b.pref) - 1) {
while (0 <= p - 1 && (b.pref[i].fi | a.suf[p - 1].fi) == full) {
if (p != ss(a.suf)) s -= a.suf[p].se;
p--;
}
if (p != ss(a.suf)) c.ans = min(c.ans, s + s2 + 1 + (1 - a.suf[p].se));
s2 += b.pref[i].se;
}
LL last = 0LL;
int cnt = 0;
for (auto it : a.pref) {
if ((it.fi | last) != last) {
if (cnt) c.pref.pb({last, cnt});
last = it.fi | last;cnt = it.se;
}
else cnt += it.se;
}
for (auto it : b.pref) {
if ((it.fi | last) != last) {
if (cnt) c.pref.pb({last, cnt});
last = it.fi | last;cnt = it.se;
}
else cnt += it.se;
}
c.pref.pb({last, cnt});
last = 0LL;
cnt = 0;
for (auto it : b.suf) {
if ((it.fi | last) != last) {
if (cnt) c.suf.pb({last, cnt});
last = it.fi | last;cnt = it.se;
}
else cnt += it.se;
}
for (auto it : a.suf) {
if ((it.fi | last) != last) {
if (cnt) c.suf.pb({last, cnt});
last = it.fi | last;cnt = it.se;
}
else cnt += it.se;
}
c.suf.pb({last, cnt});
return c;
}
void update(int x, int c) {
x += pod;
t[x] = gao(c);
x /= 2;
while (x) {
t[x] = merge(t[2 * x], t[2 * x + 1]);
x /= 2;
}
}
int main() {
scanf ("%d%d%d", &n, &k, &m);
full = (1LL << k) - 1;
rep(i, 1, n) {
scanf ("%d", d + i);
d[i]--;
}
rep(i, 0, pod - 1) {
if (1 <= i && i <= n) t[i + pod] = gao(d[i]);
else t[i + pod] = gao(-1);
}
per(i, 1, pod - 1) t[i] = merge(t[2 * i], t[2 * i + 1]);
while (m--) {
scanf ("%d", &a);
if (a == 2) {
int w = t[1].ans;
if (w == INF) w = -1;
printf ("%d\n", w);
}
else {
scanf ("%d%d", &b, &e);
e--;
update(b, e);
}
assert(ss(t[1].pref) <= k);
assert(ss(t[1].suf) <= k);
}
return 0;
}
Compilation message
nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d", &n, &k, &m);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:125:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", d + i);
~~~~~~^~~~~~~~~~~~~
nekameleoni.cpp:135:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &a);
~~~~~~^~~~~~~~~~
nekameleoni.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &b, &e);
~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
23416 KB |
Output is correct |
| 2 |
Correct |
48 ms |
23288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
23804 KB |
Output is correct |
| 2 |
Correct |
78 ms |
23544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
118 ms |
24056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
727 ms |
27576 KB |
Output is correct |
| 2 |
Correct |
1785 ms |
38264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1012 ms |
35192 KB |
Output is correct |
| 2 |
Correct |
1864 ms |
43440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1406 ms |
32376 KB |
Output is correct |
| 2 |
Correct |
1945 ms |
40748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1654 ms |
37752 KB |
Output is correct |
| 2 |
Correct |
1987 ms |
41464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1751 ms |
36664 KB |
Output is correct |
| 2 |
Correct |
1971 ms |
42616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2058 ms |
45644 KB |
Output is correct |
| 2 |
Correct |
2126 ms |
45688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2027 ms |
45560 KB |
Output is correct |
| 2 |
Correct |
1988 ms |
45820 KB |
Output is correct |
