#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, K, Q;
const int INF = 1e9;
struct Node{
int ans;
vector<pair<ll, int>> L, R;
Node(){}
Node(int _ans, int _k, int _p){ans = _ans; L.push_back({1LL << _k, _p}); R.push_back({1LL << _k, _p});}
};
Node f(Node &p, Node &q){
Node ret; ret.ans = min(p.ans, q.ans);
for(ll i = p.R.size() - 1, j = 0; i >= 0 && j < q.L.size(); i--){
while(j < q.L.size() && (p.R[i].first | q.L[j].first) != (1 << K) - 1) j++;
if(j < q.L.size()) ret.ans = min(ret.ans, q.L[j].second - p.R[i].second + 1);
}
ret.L = p.L, ret.R = q.R;
for(ll i = 0; i < q.L.size(); i++){
if((ret.L.back().first | q.L[i].first) > ret.L.back().first){
ret.L.push_back({ret.L.back().first | q.L[i].first, q.L[i].second});
}
}
for(ll i = 0; i < p.R.size(); i++){
if((ret.R.back().first | p.R[i].first) > ret.R.back().first){
ret.R.push_back({ret.R.back().first | p.R[i].first, p.R[i].second});
}
}
return ret;
}
Node T[400005];
void init(int n, int s, int e){
if(s == e){
T[n] = Node(K == 1 ? 1 : INF, 0, s);
return;
}
ll m = (s + e) / 2;
init(n * 2, s, m); init(n * 2 + 1, m + 1, e);
T[n] = f(T[n * 2], T[n * 2 + 1]);
}
void update(int n, int s, int e, int k, int v){
if(s == e){
T[n] = Node(K == 1 ? 1 : INF, v, s);
return;
}
int m = (s + e) / 2;
if(k <= m) update(n * 2, s, m, k, v);
else update(n * 2 + 1, m + 1, e, k, v);
T[n] = f(T[n * 2], T[n * 2 + 1]);
}
int main(){
cin.tie(0) -> sync_with_stdio(false);
cin >> N >> K >> Q;
init(1, 1, N);
for(int i = 1; i <= N; i++){
int v; cin >> v; v--;
update(1, 1, N, i, v);
}
while(Q--){
int op; cin >> op;
if(op == 1){
int k, v; cin >> k >> v; v--;
update(1, 1, N, k, v);
} else {
cout << (T[1].ans > N ? -1 : T[1].ans) << '\n';
}
}
}
Compilation message
nekameleoni.cpp: In function 'Node f(Node&, Node&)':
nekameleoni.cpp:15:51: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(ll i = p.R.size() - 1, j = 0; i >= 0 && j < q.L.size(); i--){
| ~~^~~~~~~~~~~~
nekameleoni.cpp:16:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | while(j < q.L.size() && (p.R[i].first | q.L[j].first) != (1 << K) - 1) j++;
| ~~^~~~~~~~~~~~
nekameleoni.cpp:17:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | if(j < q.L.size()) ret.ans = min(ret.ans, q.L[j].second - p.R[i].second + 1);
| ~~^~~~~~~~~~~~
nekameleoni.cpp:20:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(ll i = 0; i < q.L.size(); i++){
| ~~^~~~~~~~~~~~
nekameleoni.cpp:25:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(ll i = 0; i < p.R.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
23252 KB |
Output is correct |
| 2 |
Correct |
29 ms |
23020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
23628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
24112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
407 ms |
29776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
831 ms |
41144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
865 ms |
37028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1212 ms |
43932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1131 ms |
42812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1655 ms |
56764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1705 ms |
56824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
