#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, c;
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}};
}
}
};
vector <pair<LL, int>> pp;
gao t[2 * pod];
gao merge(const gao& a, const gao& b) {
gao c;
c.ans = min(a.ans, b.ans);
c.pref = c.suf = {};
c.sum = a.sum + b.sum;
int p = ss(a.suf);
int s = a.sum;
int 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;
pp = a.pref;
for (auto it : b.pref) pp.pb(it);
for (auto it : pp) {
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;
pp = b.suf;
for (auto it : a.suf) pp.pb(it);
for (auto it : pp) {
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, &c);
c--;
update(b, c);
}
}
return 0;
}
Compilation message
nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:116: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:119:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", d + i);
~~~~~~^~~~~~~~~~~~~
nekameleoni.cpp:129:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &a);
~~~~~~^~~~~~~~~~
nekameleoni.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &b, &c);
~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
23544 KB |
Output is correct |
| 2 |
Correct |
65 ms |
23420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
110 ms |
23928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
24184 KB |
Output is correct |
| 2 |
Correct |
191 ms |
24184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1226 ms |
28536 KB |
Output is correct |
| 2 |
Execution timed out |
3098 ms |
41440 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1636 ms |
37496 KB |
Output is correct |
| 2 |
Execution timed out |
3101 ms |
47352 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2333 ms |
34296 KB |
Output is correct |
| 2 |
Execution timed out |
3101 ms |
44152 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2754 ms |
40724 KB |
Output is correct |
| 2 |
Execution timed out |
3095 ms |
46200 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2678 ms |
39416 KB |
Output is correct |
| 2 |
Execution timed out |
3099 ms |
47608 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3101 ms |
49912 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3095 ms |
49924 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
