#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
int n, k, m;
const int INF = 1e9;
struct Node {
vi pref, suf;
int ans = INF, len;
};
class SegmentTree {
private:
vector<Node> tree; vi raw; int n;
Node bound;
Node merge(Node a, Node b) {
Node curr = bound;
curr.ans = min(a.ans, b.ans);
curr.len = a.len+b.len;
curr.pref = a.pref; curr.suf = b.suf;
bool valid = true;
for_(i, 0, k) {
curr.pref[i] = min(curr.pref[i], b.pref[i]+a.len);
curr.suf[i] = min(curr.suf[i], a.suf[i]+b.len);
if (curr.pref[i] == INF) valid = false;
}
if (valid) {
vector<ii> seq(k);
for_(i, 0, k) seq[i] = {a.suf[i], i};
sort(seq.begin(), seq.end());
vi sufMax(k);
for (int i = k-1; i >= 0; i--) {
sufMax[i] = b.pref[seq[i].second];
if (i < k-1) sufMax[i] = max(sufMax[i], sufMax[i+1]);
}
for_(i, 0, k-1) curr.ans = min(curr.ans, seq[i].first + sufMax[i+1]);
}
return curr;
}
void buildTree(int l, int r, int p) {
if (l == r) {
tree[p] = bound;
if (raw[l] < k) {
tree[p].pref[raw[l]] = 1;
tree[p].suf[raw[l]] = 1;
}
if (k == 1 and raw[l] == 1) tree[p].ans = 1;
return;
}
int mid = (l + r) / 2;
int c1 = 2*p+1, c2 = 2*p+2;
buildTree(l, mid, c1); buildTree(mid+1, r, c2);
tree[p] = merge(tree[c1], tree[c2]);
}
void update(int i, int val, int l, int r, int p) {
if (l > i or r < i) return;
if (l == r) {
tree[p] = bound;
if (val < k) {
tree[p].pref[val] = 1;
tree[p].suf[val] = 1;
}
if (k == 1 and val == 1) tree[p].ans = 1;
return;
}
int mid = (l + r) / 2;
int c1 = 2*p+1, c2 = 2*p+2;
update(i, val, l, mid, c1); update(i, val, mid+1, r, c2);
tree[p] = merge(tree[c1], tree[c2]);
}
//Node ans(int i, int j, int l, int r, int p) {
//if (l > j or r < i) return bound;
//if (l >= i and r <= j) return tree[p];
//int mid = (l + r) / 2;
//int c1 = 2*p+1, c2 = 2*p+2;
//return merge(ans(i, j, l, mid, c1), ans(i, j, mid+1, r, c2));
//}
public:
SegmentTree(vi input) {
raw = input;
n = raw.size();
tree.resize(4*n);
bound.pref.resize(k, INF); bound.suf.resize(k, INF); bound.len = 1;
buildTree(0, n-1, 0);
}
int ans(int i, int j) {
return tree[0].ans;
}
void update(int i, int val) {
update(i, val, 0, n-1, 0);
}
};
int main() {
#ifdef shiven
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> m;
vi nums(n);
for_(i, 0, n) {
cin >> nums[i];
nums[i] -= 1;
}
SegmentTree tree(nums);
for_(q, 0, m) {
int t; cin >> t;
if (t == 2) {
int ans = tree.ans(0, n-1);
if (ans == INF) cout << -1;
else cout << ans;
cout << endl;
} else {
int p, v; cin >> p >> v;
tree.update(p-1, v-1);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
2176 KB |
Output is correct |
| 2 |
Correct |
14 ms |
2176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
3832 KB |
Output is correct |
| 2 |
Correct |
32 ms |
3712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
5632 KB |
Output is correct |
| 2 |
Correct |
47 ms |
5632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
762 ms |
22008 KB |
Output is correct |
| 2 |
Correct |
1200 ms |
74112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1162 ms |
57212 KB |
Output is correct |
| 2 |
Correct |
1287 ms |
99064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1573 ms |
43920 KB |
Output is correct |
| 2 |
Correct |
1311 ms |
85368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1933 ms |
68728 KB |
Output is correct |
| 2 |
Correct |
1330 ms |
89592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1895 ms |
63628 KB |
Output is correct |
| 2 |
Correct |
1340 ms |
94968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2350 ms |
104824 KB |
Output is correct |
| 2 |
Correct |
1393 ms |
105808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2380 ms |
104828 KB |
Output is correct |
| 2 |
Correct |
1380 ms |
106184 KB |
Output is correct |
