#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e5 + 5;
const ll oo = 1e9;
const int lg = 3;
const int tx = 2;
#define pii pair<int, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;
int n, k, m;
int A[nmax];
vector<int> de;
int cnt[nmax];
struct node{
int f[51], ans, g[51];
node(){
memset(f, -1, sizeof f);
memset(g, -1, sizeof g);
}
friend node operator + (const node &a, const node &b){
node res;
for(int i = 1; i <= k; ++i) res.f[i] = res.g[i] = -1;
res.ans = min(a.ans, b.ans);
for(int i = 1; i <= k; ++i){
if(b.f[i] != -1) res.f[i] = b.f[i];
else res.f[i] = a.f[i];
}
for(int i = 1; i <= k; ++i){
if(a.g[i] != -1) res.g[i] = a.g[i];
else res.g[i] = b.g[i];
}
for(int i = 1; i <= k; ++i){
if(a.f[i] != -1) de.push_back(a.f[i]);
if(b.g[i] != -1) de.push_back(b.g[i]);
}
int ma = -1, mi = oo;
for(auto p : de) ma = max(ma, p), mi = min(mi, p);
if(ma - mi + 1 > res.ans){
de.clear();
return res;
}
sort(de.begin(), de.end());
int pos = 0, cur = 0;
for(int i = 0; i < de.size(); ++i){
int p = A[de[i]];
cnt[p]++;
if(cnt[p] == 1) ++cur;
if(cnt[A[de[pos]]] == 2){
cnt[A[de[pos]]]--;
pos++;
}
// cout << pos << ' ';
if(cur == k) res.ans = min(res.ans, de[i] - de[pos] + 1);
}
for(auto p : de) cnt[A[p]] = 0;
de.clear();
return res;
}
}st[1 << 18];
void update(int id, int l, int r, int u, int val){
if(l > u || r < u) return;
if(l == r){
if(k == 1) st[id].ans = 1;
else st[id].ans = oo;
st[id].f[A[l]] = -1;
st[id].f[val] = l;
st[id].g[A[l]] = -1;
st[id].g[val] = l;
A[l] = val;
return;
}
int mid = r + l >> 1;
update(id << 1, l, mid, u, val);
update(id << 1 | 1, mid + 1, r, u, val);
st[id] = st[id << 1] + st[id << 1 | 1];
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> k >> m;
for(int i = 1; i <= n; ++i) cin >> A[i];
for(int i = 1; i <= n; ++i){
update(1, 1, n, i, A[i]);
}
// for(int i = 1; i <= k; ++i){
// cout << st[1].g[i] << ' ';
// }
while(m--){
int t;
cin >> t;
if(t == 1){
int u, v;
cin >> u >> v;
update(1, 1, n, u, v);
// for(int i = 1; i <= n; ++i)
}
else{
if(st[1].ans == oo) cout << -1 << "\n";
else cout << st[1].ans << "\n";
}
}
}
/*
7 4 2
4 4 2 1 3 2 1
1 4 4
2
*/
Compilation message
nekameleoni.cpp: In function 'node operator+(const node&, const node&)':
nekameleoni.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < de.size(); ++i){
| ~~^~~~~~~~~~~
nekameleoni.cpp: In function 'void update(int, int, int, int, int)':
nekameleoni.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | int mid = r + l >> 1;
| ~~^~~
nekameleoni.cpp: At global scope:
nekameleoni.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
88 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
106076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
106072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
106072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
471 ms |
106584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
680 ms |
106720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
885 ms |
106908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1073 ms |
107464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1038 ms |
107484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1286 ms |
107772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1288 ms |
107836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
