#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 ans;
vector<int> f, g;
friend node operator + (const node &a, const node &b){
node res;
res.ans = min(a.ans, b.ans);
de.clear();
de.resize(a.f.size() + b.g.size());
merge(a.f.begin(), a.f.end(), b.g.begin(), b.g.end(), de.begin());
for(int i = 0; i < de.size(); ++i){
int x = A[de[i]];
if(++cnt[x] == 1) res.g.push_back(de[i]);
// cout << de[i] << ' ';
}
// cout << "\n";
for(int i = 1; i <= k; ++i) cnt[i] = 0;
for(int i = de.size() - 1; i >= 0; --i){
int x = A[de[i]];
if(++cnt[x] == 1) res.f.push_back(de[i]);
}
reverse(res.f.begin(), res.f.end());
for(int i = 1; i <= k; ++i) cnt[i] = 0;
int pos = 0, cur = 0;
for(int i = 0; i < de.size(); ++i){
// cout << de[i] << ' ';
int p = A[de[i]];
cnt[p]++;
if(cnt[p] == 1) ++cur;
while(cnt[A[de[pos]]] == 2){
cnt[A[de[pos]]]--;
pos++;
}
if(cur == k) res.ans = min(res.ans, de[i] - de[pos] + 1);
}
// cout << "\n";
for(auto p : de) cnt[A[p]] = 0;
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.clear();
st[id].g.clear();
st[id].f.push_back(l);
st[id].g.push_back(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:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < de.size(); ++i){
| ~~^~~~~~~~~~~
nekameleoni.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0; i < de.size(); ++i){
| ~~^~~~~~~~~~~
nekameleoni.cpp: In function 'void update(int, int, int, int, int)':
nekameleoni.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid = r + l >> 1;
| ~~^~~
nekameleoni.cpp: At global scope:
nekameleoni.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
82 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
15452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
15700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
15704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
647 ms |
19280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1251 ms |
24596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1266 ms |
22868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1773 ms |
26376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1690 ms |
25928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2478 ms |
32948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2542 ms |
33152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
