#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);
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;
while(cnt[A[de[pos]]] == 2){
cnt[A[de[pos]]]--;
pos++;
}
// cout << p << ' ';
if(cur == k) res.ans = min(res.ans, de[i] - de[pos] + 1);
}
// cout << "\n";
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";
}
}
}
/*
8 5 2
1 3 4 4 4 2 5 3
1 4 1
2
2
*/
Compilation message
nekameleoni.cpp: In function 'node operator+(const node&, const node&)':
nekameleoni.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i = 0; i < de.size(); ++i){
| ~~^~~~~~~~~~~
nekameleoni.cpp: In function 'void update(int, int, int, int, int)':
nekameleoni.cpp:78:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int mid = r + l >> 1;
| ~~^~~
nekameleoni.cpp: At global scope:
nekameleoni.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
85 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
106068 KB |
Output is correct |
| 2 |
Correct |
34 ms |
106076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
106076 KB |
Output is correct |
| 2 |
Correct |
80 ms |
106064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
106144 KB |
Output is correct |
| 2 |
Correct |
154 ms |
106064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1162 ms |
106248 KB |
Output is correct |
| 2 |
Execution timed out |
3064 ms |
107548 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2106 ms |
106592 KB |
Output is correct |
| 2 |
Execution timed out |
3013 ms |
107768 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2418 ms |
106340 KB |
Output is correct |
| 2 |
Execution timed out |
3013 ms |
107472 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3057 ms |
106644 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3038 ms |
106448 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3098 ms |
106576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3055 ms |
106580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
