This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ld long double
#define x first
#define y second
#define mp make_pair
#define bug cout << "There\n";
const ll MAXN = 1e5 + 1, MAXM = 5e2 + 1, INF = 1e9, MOD = 1e9 + 7, CMOD = 998244353;
const ll P = 263, P2 = 570210983;
const ld eps = 1e-10;
using namespace std;
int n, k, m;
struct node{
vector<pair<ll, ll>> pref, suff;
};
struct seg_tree{
int ans[MAXN * 4];
node t[MAXN * 4];
void mg(int a, int b, int c, int pos){
t[a].pref.clear(), t[a].suff.clear();
ans[a] = min(ans[b], ans[c]);
int uk, lenpref = t[b].pref.size(), lensuff2 = t[b].suff.size(), lensuff = t[c].suff.size(), lenpref2 = t[c].pref.size();
uk = lenpref;
ll mask = 0, mask2 = 0;
for (int i = 0; i < lenpref; i++){
mask |= (1ll << t[b].pref[i].x);
}
for (int i = 0; i < lensuff; i++){
mask2 |= (1ll << t[c].suff[i].x);
while (uk - 1 >= 0){
ll xr = 0;
if (uk != lenpref){
xr = (1ll << t[b].pref[uk].x);
}
if (((xr ^ mask) | mask2) == (1ll << k) - 1){
--uk;
}
else{
break;
}
}
if (uk != lenpref){
ans[a] = min(ans[a] * 1ll, t[c].suff[i].y - t[b].pref[uk].y + 1);
}
}
//building pref
bool was[k + 1];
for (int i = 0; i < k; i++){
was[i] = 0;
}
for (int i = 0; i < lenpref2; i++){
t[a].pref.pb(t[c].pref[i]);
was[t[c].pref[i].x] = 1;
}
for (int i = 0; i < lenpref; i++){
if (was[t[b].pref[i].x] == 0)
t[a].pref.pb(t[b].pref[i]);
}
for (int i = 0; i < k; i++){
was[i] = 0;
}
for (int i = 0; i < lensuff2; i++){
t[a].suff.pb(t[b].suff[i]);
was[t[b].suff[i].x] = 1;
}
for (int i = 0; i < lensuff; i++){
if (was[t[c].suff[i].x] == 0)
t[a].suff.pb(t[c].suff[i]);
}
}
void upd(int pos, int val, int posik, int v = 1, int tl = 1, int tr = n){
if (tl == tr){
ans[v] = (k == 1 ? 1 : INF);
t[v].pref.clear(), t[v].suff.clear();
t[v].pref.pb(mp(val, tl));
t[v].suff.pb(mp(val, tl));
return;
}
int tm = (tl + tr) >> 1;
if (pos <= tm)
upd(pos, val, posik, v + v, tl, tm);
else
upd(pos, val, posik, v + v + 1, tm + 1, tr);
mg(v, v + v, v + v + 1, posik);
}
int get(){
return ans[1];
}
} rt;
main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
cin >> n >> k >> m;
for (int i = 1, x; i <= n; ++i){
cin >> x;
--x;
rt.upd(i, x, 0);
}
for (int i = 1, type, pos, val; i <= m; i++){
cin >> type;
if (type == 1){
cin >> pos >> val;
--val;
rt.upd(pos, val, i);
}
else{
int ans = rt.get();
cout << (ans == INF ? -1 : ans) << '\n';
}
}
}
/*
*/
Compilation message (stderr)
nekameleoni.cpp:94:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
94 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |