//https://hsin.hr/coci/archive/2015_2016/results.php?contest=3
//Lovro Pužar
#define NDEBUG
#include <algorithm>
#include <climits>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
#define repeat(n) for (int repc = (n); repc > 0; --repc)
template<typename T, typename U> inline bool makemin(T &res, const U &x) {
if (x < res) {
res = x;
return true;
}
return false;
}
template<typename T, typename U> inline bool makemax(T &res, const U &x) {
if (x > res) {
res = x;
return true;
}
return false;
}
const int MAXN = 100005;
const int MAXK = 50;
int K;
struct TournamentTree {
TournamentTree(int n) : n(n), nodes_(4*n) { }
void update(int pos, int upd, bool defer) {
update(0, 1, n, pos, upd, defer);
}
void build() {
build(0, 1, n);
}
int query() {
return nodes_[0].ans_;
}
private:
struct Node {
Node() {
for (int k=1; k<=K; ++k) {
minp[k] = INT_MAX;
maxp[k] = INT_MIN;
}
}
void set_single(int pos, int val) {
if (val_ != -1) {
minp[val_] = INT_MAX;
maxp[val_] = INT_MIN;
}
val_ = val;
minp[val] = maxp[val] = pos;
ans_ = K == 1 ? 1 : INT_MAX;
}
int val_ = -1;
int minp[MAXK+1], maxp[MAXK+1];
int ans_;
};
void update(int node, int a, int b, int pos, int val, bool defer) {
if (a == pos && b == pos) {
nodes_[node].set_single(pos, val);
return;
}
int mid = (a+b) / 2;
if (pos <= mid) {
update(2*node+1, a, mid, pos, val, defer);
} else {
update(2*node+2, mid+1, b, pos, val, defer);
}
if (!defer) {
merge(nodes_[node], nodes_[2*node+1], nodes_[2*node+2]);
// fprintf(stderr, "merge(a=%d, b=%d) => %d\n", a, b, nodes_[node].ans_);
}
}
void build(int node, int a, int b) {
if (a < b) {
int mid = (a+b) / 2;
build(2*node+1, a, mid);
build(2*node+2, mid+1, b);
// fprintf(stderr, "merge(a=%d, b=%d) ...\n", a, b);
merge(nodes_[node], nodes_[2*node+1], nodes_[2*node+2]);
// fprintf(stderr, "build(a=%d, b=%d) => %d\n", a, b, nodes_[node].ans_);
}
}
void merge(Node& out, const Node& in1, const Node& in2) {
out.ans_ = min(in1.ans_, in2.ans_);
for (int k=1; k<=K; ++k) {
out.minp[k] = min(in1.minp[k], in2.minp[k]);
out.maxp[k] = max(in1.maxp[k], in2.maxp[k]);
}
static vector<pair<int, int> > vp;
vp.clear();
int right = -1;
for (int k=1; k<=K; ++k) {
if (in1.maxp[k] != INT_MIN) {
vp.push_back(make_pair(in1.maxp[k], k));
} else if (in2.minp[k] != INT_MAX) {
makemax(right, in2.minp[k]);
} else {
return;
}
}
sort(vp.begin(), vp.end());
for (int i=0; i<(int)vp.size(); ++i) {
int maxp, k;
tie(maxp, k) = vp[i];
// fprintf(stderr, " k = %d, right = %d, maxp = %d\n", k, right, maxp);
if (right != -1) {
makemin(out.ans_, right - maxp + 1);
}
if (in2.minp[k] == INT_MAX) {
break;
}
makemax(right, in2.minp[k]);
}
}
int n;
vector<Node> nodes_;
};
int main() {
ios_base::sync_with_stdio(0); // caret here
int N, M;
cin >> N >> K >> M;
TournamentTree tt(N);
for (int i=0; i<N; ++i) {
int val;
cin >> val;
tt.update(i+1, val, true);
}
tt.build();
repeat (M) {
int type;
cin >> type;
if (type == 1) {
int p, v;
cin >> p >> v;
tt.update(p, v, false);
} else if (type == 2) {
int ans = tt.query();
cout << (ans <= N ? ans : -1) << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
8456 KB |
Output is correct |
| 2 |
Correct |
12 ms |
8404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
461 ms |
33612 KB |
Output is correct |
| 2 |
Correct |
277 ms |
115148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
735 ms |
88976 KB |
Output is correct |
| 2 |
Correct |
326 ms |
154020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1014 ms |
67844 KB |
Output is correct |
| 2 |
Correct |
329 ms |
132936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1190 ms |
106880 KB |
Output is correct |
| 2 |
Correct |
423 ms |
139440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1239 ms |
99224 KB |
Output is correct |
| 2 |
Correct |
374 ms |
147756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1481 ms |
163444 KB |
Output is correct |
| 2 |
Correct |
356 ms |
163164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1427 ms |
163140 KB |
Output is correct |
| 2 |
Correct |
345 ms |
163160 KB |
Output is correct |
