#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=int;
const ll maxN=1e5+10;
const ll inf=1e9;
const ll mod=1e9+7;
ll k;
ll cnt[51];
struct node
{
ll val;
pli pre[51],suf[51];
ll l,r;
node ()
{
val=inf;
pre[0].fi=0;
suf[0].fi=0;
for(int i=1;i<=k;i++) pre[i]={inf,i},suf[i]={inf,i};
}
node operator+(const node&o)
{
node ans;
ans.l=l;
ans.r=o.r;
ans.val=min(val,o.val);
fill(cnt+1,cnt+k+1,1);
ll j=1;
ll dem=0;
ans.val=min(ans.val,o.pre[k].fi);
for(int i=k;i>=1;i--)
{
cnt[o.pre[i].se]--;
if(cnt[o.pre[i].se]==0) dem++;
while(dem>0)
{
cnt[suf[j].se]++;
if(cnt[suf[j].se]==1) dem--;
j++;
}
ans.val=min(ans.val,o.pre[i-1].fi+suf[j-1].fi);
}
fill(cnt,cnt+k+1,0);
dem=0;
for(int i=1;i<=k;i++)
{
if(o.suf[i].fi!=inf)
{
dem++;
ans.suf[i].fi=o.suf[i].fi;
ans.suf[i].se=o.suf[i].se;
cnt[ans.suf[i].se]=1;
}
else break;
}
for(int i=1;i<=k;i++)
{
if(cnt[suf[i].se]==0)
{
dem++;
ans.suf[dem].fi=min(inf,suf[i].fi+o.r-o.l+1);
ans.suf[dem].se=suf[i].se;
}
}
fill(cnt,cnt+k+1,0);
dem=0;
for(int i=1;i<=k;i++)
{
if(pre[i].fi!=inf)
{
dem++;
ans.pre[i].fi=pre[i].fi;
ans.pre[i].se=pre[i].se;
cnt[ans.pre[i].se]=1;
}
else break;
}
for(int i=1;i<=k;i++)
{
if(cnt[o.pre[i].se]==0)
{
cnt[o.pre[i].se]=1;
dem++;
ans.pre[dem].fi=min(inf,o.pre[i].fi+r-l+1);
ans.pre[dem].se=o.pre[i].se;
}
}
return ans;
}
}st[4*maxN];
ll a[maxN];
ll n,m;
void build(ll id=1,ll l=1,ll r=n)
{
if(l==r)
{
st[id]=node();
if(k==1) st[id].val=1;
st[id].pre[1]={1,a[l]};
st[id].suf[1]={1,a[l]};
st[id].l=l;
st[id].r=r;
ll j=1;
for(int i=2;i<=k;i++)
{
if(j==a[l]) j++;
st[id].pre[i]={inf,j};
st[id].suf[i]={inf,j};
j++;
}
return;
}
ll mid=l+r>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
void update(ll pos,ll val,ll id=1,ll l=1,ll r=n)
{
if(l==r)
{
st[id]=node();
if(k==1) st[id].val=1;
st[id].pre[1]={1,val};
st[id].suf[1]={1,val};
st[id].l=l;
st[id].r=r;
ll j=1;
for(int i=2;i<=k;i++)
{
if(j==val) j++;
st[id].pre[i]={inf,j};
st[id].suf[i]={inf,j};
j++;
}
return;
}
ll mid=l+r>>1;
if(pos<=mid) update(pos,val,id*2,l,mid);
else update(pos,val,id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
void solve()
{
cin >> n >> k >> m;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
build();
for(int i=1;i<=m;i++)
{
ll t;
cin >> t;
if(t==1)
{
ll p,s;
cin >> p >> s;
update(p,s);
}
else
{
if(st[1].val!=inf) cout << st[1].val<<'\n';
else cout << -1<<'\n';
}
}
/*for(int id=1;id<=4*n;id++)
{
cout << st[id].l<<' '<<st[id].r<<' '<<st[id].val<<'\n';
for(int i=1;i<=k;i++) cout << st[id].pre[i].fi<<' ';
cout << '\n';
for(int i=1;i<=k;i++) cout << st[id].suf[i].fi<<' ';
cout << '\n'<<'\n';;
}*/
//cout <<st[5].pre[1].se<<'\n';
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
nekameleoni.cpp: In function 'void build(ll, ll, ll)':
nekameleoni.cpp:119:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
119 | ll mid=l+r>>1;
| ~^~
nekameleoni.cpp: In function 'void update(ll, ll, ll, ll, ll)':
nekameleoni.cpp:144:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
144 | ll mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
324424 KB |
Output is correct |
| 2 |
Correct |
157 ms |
324420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
324556 KB |
Output is correct |
| 2 |
Correct |
185 ms |
324408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
324472 KB |
Output is correct |
| 2 |
Correct |
197 ms |
324428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
657 ms |
325008 KB |
Output is correct |
| 2 |
Correct |
1721 ms |
325844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
865 ms |
325244 KB |
Output is correct |
| 2 |
Correct |
1799 ms |
326088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1147 ms |
325588 KB |
Output is correct |
| 2 |
Correct |
1855 ms |
325932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1327 ms |
325736 KB |
Output is correct |
| 2 |
Correct |
1822 ms |
325984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1284 ms |
325752 KB |
Output is correct |
| 2 |
Correct |
1901 ms |
326036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1556 ms |
326132 KB |
Output is correct |
| 2 |
Correct |
1884 ms |
326076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1555 ms |
325944 KB |
Output is correct |
| 2 |
Correct |
1897 ms |
326084 KB |
Output is correct |
