#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
int readInt() {
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while(true) {
if(ch == '-') break;
if(ch >= '0' && ch <= '9') break;
ch = getchar();
}
if(ch == '-') minus = true; else result = ch - '0';
while(true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result * 10 + (ch - '0');
}
if(minus)
return -result;
else
return result;
}
const int MAXN = 100005;
struct SegNode {
vector<int> pre, suf;
int best;
} seg[4 * MAXN];
int val[MAXN], cnt[MAXN], nArr, k, numQuery;
void mergeNode(SegNode &res, const SegNode &a, const SegNode &b) {
res.pre = a.pre, res.suf = b.suf;
res.best = min(a.best, b.best);
for (int i = 1; i <= k; ++i)
cnt[i] = 0;
for (int it = 0; it < int(a.pre.size()); ++it)
cnt[val[a.pre[it]]] = 1;
for (int it = 0; it < int(b.pre.size()); ++it) {
if(!cnt[val[b.pre[it]]]) {
cnt[val[b.pre[it]]] = 1;
res.pre.push_back(b.pre[it]);
}
}
if(res.pre.size() == k)
res.best = min(res.best, res.pre.back() - res.pre[0] + 1);
for (int i = 1; i <= k; ++i)
cnt[i] = 0;
for (int it = 0; it < int(b.suf.size()); ++it)
cnt[val[b.suf[it]]] = 1;
for (int it = 0; it < int(a.suf.size()); ++it) {
if(!cnt[val[a.suf[it]]]) {
cnt[val[a.suf[it]]] = 1;
res.suf.push_back(a.suf[it]);
}
}
if(res.suf.size() == k)
res.best = min(res.best, res.suf[0] - res.suf.back() + 1);
for (int i = 1; i <= k; ++i)
cnt[i] = 0;
for (int it = 0; it < int(b.pre.size()); ++it)
++cnt[val[b.pre[it]]];
int cntNum(b.pre.size()), j(int(b.pre.size()) - 1);
for (int it = 0; it < int(a.suf.size()); ++it) {
cntNum += (++cnt[val[a.suf[it]]] == 1);
while(j >= 0 && cntNum == k && cnt[val[b.pre[j]]] > 1) {
--cnt[val[b.pre[j]]];
--j;
}
if(cntNum == k) {
res.best = min(res.best, (j >= 0 ? b.pre[j] : a.suf[0]) - a.suf[it] + 1);
//cout << (j >= 0 ? b.pre[j] : a.suf[0]) << ' ' << a.suf[it] << '\n';
}
}
//cout << res.best << '\n';
}
void build(int id, int l, int r) {
if(l == r) {
seg[id].pre.push_back(l);
seg[id].suf.push_back(l);
seg[id].best = (k == 1) ? 1 : 1e9+7;
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
//cout << l << ' ' << r << ":\n";
mergeNode(seg[id], seg[id << 1], seg[id << 1 | 1]);
}
void update(int pos, int val) {
int id(1), l(1), r(nArr);
while(l != r) {
int mid = (l + r) >> 1;
if(pos <= mid) {
id = id << 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
while(id > 1) {
id >>= 1;
mergeNode(seg[id], seg[id << 1], seg[id << 1 | 1]);
}
}
void process() {
cin >> nArr >> k >> numQuery;
for (int i = 1; i <= nArr; ++i) {
cin >> val[i];
}
build(1, 1, nArr);
for (int t = 0; t < numQuery; ++t) {
int type, pos, v;
cin >> type;
if(type == 1) {
cin >> pos >> v;
val[pos] = v;
update(pos, v);
} else {
cout << (seg[1].best >= 1e9 ? -1 : seg[1].best) << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("nekameleoni.inp", "r", stdin);
// freopen("nekameleoni.out", "w", stdout);
process();
return 0;
}
Compilation message
nekameleoni.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("O3")
|
nekameleoni.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
7 | #pragma GCC optimization ("unroll-loops")
|
nekameleoni.cpp: In function 'void mergeNode(SegNode&, const SegNode&, const SegNode&)':
nekameleoni.cpp:73:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
73 | if(res.pre.size() == k)
| ~~~~~~~~~~~~~~~^~~~
nekameleoni.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
89 | if(res.suf.size() == k)
| ~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
22664 KB |
Output is correct |
| 2 |
Correct |
17 ms |
22780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
22960 KB |
Output is correct |
| 2 |
Correct |
32 ms |
22960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
23108 KB |
Output is correct |
| 2 |
Correct |
48 ms |
23212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
425 ms |
26092 KB |
Output is correct |
| 2 |
Correct |
1104 ms |
34764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
649 ms |
31864 KB |
Output is correct |
| 2 |
Correct |
1129 ms |
38680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
892 ms |
30048 KB |
Output is correct |
| 2 |
Correct |
1202 ms |
36788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1100 ms |
33996 KB |
Output is correct |
| 2 |
Correct |
1205 ms |
37440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1105 ms |
33140 KB |
Output is correct |
| 2 |
Correct |
1249 ms |
38092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1383 ms |
39372 KB |
Output is correct |
| 2 |
Correct |
1247 ms |
39432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1417 ms |
39416 KB |
Output is correct |
| 2 |
Correct |
1313 ms |
39416 KB |
Output is correct |
