#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;
bool ok = 0;
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.g.size() + b.g.size());
merge(a.g.begin(), a.g.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;
de.clear();
de.resize(a.f.size() + b.f.size());
merge(a.f.begin(), a.f.end(), b.f.begin(), b.f.end(), de.begin());
for(int i = de.size() - 1; i >= 0; --i){
int x = A[de[i]];
if(++cnt[x] == 1) res.f.push_back(de[i]);
}
// if(res.f.size())
reverse(res.f.begin(), res.f.end());
for(int i = 1; i <= k; ++i) cnt[i] = 0;
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());
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++;
}
if(cur == k) res.ans = min(res.ans, de[i] - de[pos] + 1);
}
// for(auto p : de) cout << A[p] << ' ';
// 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]);
}
ok = 1;
// 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 4 1
2 1 4 4 3 3 1 1
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: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 |
Correct |
35 ms |
15444 KB |
Output is correct |
| 2 |
Correct |
30 ms |
15448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
15700 KB |
Output is correct |
| 2 |
Correct |
64 ms |
15696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
15880 KB |
Output is correct |
| 2 |
Correct |
99 ms |
15956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
686 ms |
18764 KB |
Output is correct |
| 2 |
Correct |
2215 ms |
27336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1400 ms |
24688 KB |
Output is correct |
| 2 |
Correct |
2641 ms |
31740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1442 ms |
22816 KB |
Output is correct |
| 2 |
Correct |
2529 ms |
29948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2017 ms |
26620 KB |
Output is correct |
| 2 |
Correct |
2622 ms |
30408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1904 ms |
25828 KB |
Output is correct |
| 2 |
Correct |
2710 ms |
31364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2808 ms |
32960 KB |
Output is correct |
| 2 |
Correct |
2786 ms |
32704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2830 ms |
32624 KB |
Output is correct |
| 2 |
Correct |
2837 ms |
32596 KB |
Output is correct |
