#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 5e5 + 101;
struct Node {
int ans, l, r;
vector<pair<ll,int>> toLeft, toRight;
Node() { }
};
vector<int> A;
Node sg[4*MAXN];
ll K;
Node merge(Node a, Node b) {
Node new_node;
new_node.l = a.l;
new_node.r = b.r;
new_node.ans = min(a.ans, b.ans);
int L = 0; // a.mask_left doğru gidecek
for (int R = b.toRight.size() - 1; R >= 0; R--) {
while (L < a.toLeft.size() && (a.toLeft[L].f | b.toRight[R].f) != (1LL<<K) - 1)
L++;
if ((L < a.toLeft.size()) && ((a.toLeft[L].f | b.toRight[R].f) == (1LL<<K) - 1))
new_node.ans = min(new_node.ans, b.toRight[R].s - a.toLeft[L].s + 1);
}
for (auto u : a.toRight)
new_node.toRight.push_back(u);
for (auto u : b.toRight) {
if (new_node.toRight.back().f != (a.toRight.back().f | u.f))
new_node.toRight.push_back({(a.toRight.back().f | u.f), u.s});
}
for (auto u : b.toLeft)
new_node.toLeft.push_back(u);
for (auto u : a.toLeft) {
if (new_node.toLeft.back().f != (b.toLeft.back().f | u.f))
new_node.toLeft.push_back({(b.toLeft.back().f | u.f), u.s});
}
return new_node;
}
void init(int k, int a, int b) {
if (a == b) {
sg[k].l = a;
sg[k].r = b;
sg[k].toLeft.push_back({1LL << A[a], a});
sg[k].toRight.push_back({1LL << A[a], a});
sg[k].ans = (K == 1 ? 1 : 1e8);
return ;
}
init(2*k, a, (a+b)/2);
init(2*k+1, (a+b)/2+1, b);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
void update(int k, int a, int b, int plc, int val) {
if (b < plc || a > plc)
return ;
if (a == b) {
sg[k].toLeft.clear();
sg[k].toRight.clear();
sg[k].toLeft.push_back({1LL << val, a});
sg[k].toRight.push_back({1LL << val, a});
return ;
}
update(2*k, a, (a+b)/2, plc, val);
update(2*k+1, (a+b)/2+1, b, plc, val);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
int main() {
fast
int N, M;
cin >> N >> K >> M;
A = vector<int>(N+1);
for (int i = 1; i <= N; i++) {
cin >> A[i];
A[i]--;
}
init(1, 1, N);
for (int i = 1; i <= M; i++) {
int q, p, v;
cin >> q;
if (q == 1) {
cin >> p >> v;
v--;
update(1, 1, N, p, v);
} else
cout << (sg[1].ans >= 1e8 ? -1 : sg[1].ans) << "\n";
}
}
Compilation message
nekameleoni.cpp: In function 'Node merge(Node, Node)':
nekameleoni.cpp:30:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | while (L < a.toLeft.size() && (a.toLeft[L].f | b.toRight[R].f) != (1LL<<K) - 1)
| ~~^~~~~~~~~~~~~~~~~
nekameleoni.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if ((L < a.toLeft.size()) && ((a.toLeft[L].f | b.toRight[R].f) == (1LL<<K) - 1))
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
126544 KB |
Output is correct |
| 2 |
Correct |
40 ms |
126296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
126812 KB |
Output is correct |
| 2 |
Correct |
55 ms |
126912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
128084 KB |
Output is correct |
| 2 |
Correct |
62 ms |
127548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
349 ms |
133456 KB |
Output is correct |
| 2 |
Correct |
1057 ms |
149252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
556 ms |
144952 KB |
Output is correct |
| 2 |
Correct |
1090 ms |
159248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
729 ms |
141396 KB |
Output is correct |
| 2 |
Correct |
1190 ms |
155016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
870 ms |
147724 KB |
Output is correct |
| 2 |
Correct |
1192 ms |
156408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
870 ms |
146688 KB |
Output is correct |
| 2 |
Correct |
1193 ms |
158196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1146 ms |
162100 KB |
Output is correct |
| 2 |
Correct |
1192 ms |
161332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1172 ms |
162040 KB |
Output is correct |
| 2 |
Correct |
1173 ms |
161364 KB |
Output is correct |
