#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int maxk = 51;
int n, k, q;
int a[maxn];
struct Node
{
int minPos[maxk];
int maxPos[maxk];
long long mask;
int ans;
};
Node tree[4 * maxn];
Node combine(const Node& nodeLeft, const Node& nodeRight)
{
Node res;
res.mask = (nodeLeft.mask | nodeRight.mask);
res.ans = min(nodeLeft.ans, nodeRight.ans);
for (int i = 0; i < k; ++i)
{
res.minPos[i] = min(nodeLeft.minPos[i], nodeRight.minPos[i]);
res.maxPos[i] = max(nodeLeft.maxPos[i], nodeRight.maxPos[i]);
}
if (res.mask < (1LL << k) - 1)
{
res.ans = maxn;
return res;
}
//cout << "do actual combine" << endl;
vector<pair<int, int>> fromLeft;
vector<pair<int, int>> fromRight;
for (int i = 0; i < k; ++i)
{
if (nodeLeft.maxPos[i] != -maxn)
{
fromLeft.push_back(make_pair(nodeLeft.maxPos[i], i));
}
if (nodeRight.minPos[i] != +maxn)
{
fromRight.push_back(make_pair(nodeRight.minPos[i], i));
}
}
sort(fromLeft.begin(), fromLeft.end());
sort(fromRight.begin(), fromRight.end());
/*cout << "Left " << endl;
for (int i = fromLeft.size() - 1; i >= 0; --i)
{
cout << fromLeft[i].first << " " << fromLeft[i].second << endl;
}
cout << "----------------------" << endl;
for (int i = 0; i < fromRight.size(); ++i)
{
cout << fromRight[i].first << " " << fromRight[i].second << endl;
}
cout << "----------------------" << endl;*/
long long prefMask = 0;
int cnt = 0;
for (int i = fromLeft.size() - 1; i >= 0; --i)
{
prefMask |= (1LL << fromLeft[i].second);
++cnt;
int found = 0, lastPos = -1;
long long currMask = prefMask;
for (int j = 0; j < fromRight.size(); ++j)
{
if ((currMask & (1LL << fromRight[j].second)) == 0)
{
++found;
currMask |= (1LL << fromRight[j].second);
if (cnt + found == k)
{
lastPos = fromRight[j].first;
break;
}
}
}
if (lastPos != -1)
{
res.ans = min(res.ans, lastPos - fromLeft[i].first + 1);
}
}
return res;
}
void build(int node, int l, int r)
{
if (l == r)
{
for (int i = 0; i < k; ++i)
{
tree[node].minPos[i] = +maxn;
tree[node].maxPos[i] = -maxn;
}
tree[node].mask = (1LL << a[l]);
tree[node].minPos[a[l]] = l;
tree[node].maxPos[a[l]] = l;
tree[node].ans = maxn;
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
//cout << "combine for interval " << l << " to " << r << endl;
tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
//cout << "finish for interval " << l << " to " << r << endl;
}
void update(int node, int l, int r, int pos, int val)
{
if (l == r)
{
tree[node].mask = 0;
tree[node].minPos[a[l]] = +maxn;
tree[node].maxPos[a[l]] = -maxn;
a[l] = val;
tree[node].mask = (1LL << a[l]);
tree[node].minPos[a[l]] = pos;
tree[node].maxPos[a[l]] = pos;
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
{
update(2 * node, l, mid, pos, val);
}
else
{
update(2 * node + 1, mid + 1, r, pos, val);
}
tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n >> k >> q;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
--a[i];
}
if (k == 1)
{
for (int i = 1; i <= q; ++i)
{
int type;
cin >> type;
if (type == 1)
{
int pos, val;
cin >> pos >> val;
}
else
{
cout << "0\n";
}
}
return 0;
}
build(1, 1, n);
for (int i = 1; i <= q; ++i)
{
int type;
cin >> type;
if (type == 1)
{
int pos, val;
cin >> pos >> val;
--val;
update(1, 1, n, pos, val);
}
else
{
if (tree[1].mask != (1LL << k) - 1)
{
cout << -1 << "\n";
}
else
{
cout << tree[1].ans << "\n";
}
}
}
return 0;
}
Compilation message
nekameleoni.cpp: In function 'Node combine(const Node&, const Node&)':
nekameleoni.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int j = 0; j < fromRight.size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
8876 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
138 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1810 ms |
30032 KB |
Output is correct |
| 2 |
Correct |
203 ms |
110672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2878 ms |
56884 KB |
Output is correct |
| 2 |
Correct |
225 ms |
111036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3049 ms |
57000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3025 ms |
56944 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3026 ms |
57068 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3032 ms |
110676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3009 ms |
110680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
