#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int maxk = 51;
int n, k, q;
int a[maxn];
long long allset;
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 < allset)
{
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;
long long suffMask = 0;
for (int j = 0; j < fromRight.size(); ++j)
{
suffMask |= (1LL << fromRight[j].second);
//cout << "add to right " << fromRight[j].second << " " << suffMask << endl;
}
int ptr = fromRight.size() - 1;
for (int i = fromLeft.size() - 1; i >= 0; --i)
{
prefMask |= (1LL << fromLeft[i].second);
//cout << "add to left " << fromLeft[i].second << " " << prefMask << endl;
while (ptr - 1 >= 0 && (prefMask | (suffMask ^ (1LL << fromRight[ptr].second))) == allset)
{
suffMask ^= (1LL << fromRight[ptr].second);
//cout << "remove from right " << fromRight[ptr - 1].second << " " << suffMask << endl;
--ptr;
}
if ((prefMask | suffMask) == allset)
{
//cout << "match " << i << " with " << ptr << " :: " << (prefMask | suffMask) << " :: " << prefMask << " " << suffMask << endl;
res.ans = min(res.ans, fromRight[ptr].first - 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;
}
allset = (1LL << k) - 1;
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 != allset)
{
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:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int j = 0; j < fromRight.size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
8872 KB |
Output is correct |
| 2 |
Correct |
11 ms |
8792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
649 ms |
29700 KB |
Output is correct |
| 2 |
Correct |
204 ms |
109652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1055 ms |
56256 KB |
Output is correct |
| 2 |
Correct |
221 ms |
109904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1430 ms |
56156 KB |
Output is correct |
| 2 |
Correct |
245 ms |
110900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1788 ms |
56572 KB |
Output is correct |
| 2 |
Correct |
226 ms |
110928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1775 ms |
56812 KB |
Output is correct |
| 2 |
Correct |
223 ms |
110760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2202 ms |
110036 KB |
Output is correct |
| 2 |
Correct |
256 ms |
110520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2234 ms |
110616 KB |
Output is correct |
| 2 |
Correct |
264 ms |
110908 KB |
Output is correct |
