#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, vv;
int F[nmax], last[nmax];
void update(int x, int val){
vv.push_back(x);
for(; x; x -= x&-x) F[x] += val;
}
int get(int x){
int res = 0;
for(; x <= k * 2 ; x+= x&-x) res += F[x];
return res;
}
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]);
}
sort(de.begin(), de.end());
for(int i = 1; i <= de.size(); ++i){
int p = de[i - 1];
update(last[A[p]], -1);
int l = 1, r = i;
last[A[p]] = i;
update(last[A[p]], 1);
while(l <= r){
int mid = r + l >> 1;
if(get(mid) == k){
res.ans = min(res.ans, de[i - 1] - de[mid - 1] + 1);
l = mid + 1;
}
else r = mid - 1;
}
}
for(auto p : vv) F[p] = 0;
for(auto p : de) last[A[p]] = 0;
vv.clear(),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("scc.inp", "r", stdin);
// freopen("scc.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";
}
}
}
/*
4 3 1
2 3 1 2
2
*/
Compilation message
nekameleoni.cpp: In function 'node operator+(const node&, const node&)':
nekameleoni.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 1; i <= de.size(); ++i){
| ~~^~~~~~~~~~~~
nekameleoni.cpp:61:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = r + l >> 1;
| ~~^~~
nekameleoni.cpp: In function 'void update(int, int, int, int, int)':
nekameleoni.cpp:90:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
90 | int mid = r + l >> 1;
| ~~^~~
nekameleoni.cpp: At global scope:
nekameleoni.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
97 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
106160 KB |
Output is correct |
| 2 |
Correct |
46 ms |
106072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
106188 KB |
Output is correct |
| 2 |
Correct |
140 ms |
106072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
304 ms |
106320 KB |
Output is correct |
| 2 |
Correct |
296 ms |
106208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2616 ms |
107100 KB |
Output is correct |
| 2 |
Execution timed out |
3040 ms |
106912 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3005 ms |
106720 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
106932 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3024 ms |
107016 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3003 ms |
107004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3033 ms |
106844 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3075 ms |
106836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
