#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define left 2*i+1
#define righ 2*i+2
#define mid (l+r)/2
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const ll maxn=1e5+100;
const ll inf=1e9+10;
const ll mod=1e9+7;
const ll base=27;
ll n,k,m;
ll a[maxn];
ll ans[4*maxn],len[4*maxn];
vector<pair<ll,ll>>suf[4*maxn],pre[4*maxn];
bool check(ll bit){
return (bit+1==(1ll<<k));
}
void build(ll i,ll l,ll r){
if(l==r){
len[i]=1;
ans[i]=inf;
pre[i].pb({0,0});
pre[i].pb({1,1ll<<a[r]});
suf[i].pb({0,0});
suf[i].pb({1,1ll<<a[r]});
return;
}
build(left,l,mid);
build(righ,mid+1,r);
len[i]=len[left]+len[righ];
for(auto x:pre[left])pre[i].pb(x);
ll cur=pre[left].back().second;
for(auto x:pre[righ]){
if((x.second|cur)==cur)continue;
cur|=x.second;
pre[i].pb({len[left]+x.first,cur});
}
for(auto x:suf[righ])suf[i].pb(x);
cur=suf[righ].back().second;
for(auto x:suf[left]){
if((x.second|cur)==cur)continue;
cur|=x.second;
suf[i].pb({len[righ]+x.first,cur});
}
ll p=pre[righ].size()-1;
ll s=0;
ans[i]=inf;
while(p>=0&&s<suf[left].size()){
if(check(pre[righ][p].second|suf[left][s].second)){
ans[i]=min(ans[i],pre[righ][p].first+suf[left][s].first);
p--;
}
else{
s++;
}
}
ans[i]=min(ans[i],min(ans[left],ans[righ]));
}
void upd(ll i,ll l,ll r,ll id){
if(r<id||l>id)return;
if(l==r){
pre[i].clear();
suf[i].clear();
ans[i]=inf;
pre[i].pb({0,0});
pre[i].pb({1,1ll<<a[r]});
suf[i].pb({0,0});
suf[i].pb({1,1ll<<a[r]});
return;
}
upd(left,l,mid,id);
upd(righ,mid+1,r,id);
//len[i]=len[left]+len[righ];
pre[i].clear();suf[i].clear();
for(auto x:pre[left])pre[i].pb(x);
ll cur=pre[left].back().second;
for(auto x:pre[righ]){
if((x.second|cur)==cur)continue;
cur|=x.second;
pre[i].pb({len[left]+x.first,cur});
}
for(auto x:suf[righ])suf[i].pb(x);
cur=suf[righ].back().second;
for(auto x:suf[left]){
if((x.second|cur)==cur)continue;
cur|=x.second;
suf[i].pb({len[righ]+x.first,cur});
}
ll p=pre[righ].size()-1;
ll s=0;
ans[i]=inf;
while(p>=0&&s<suf[left].size()){
if(check(pre[righ][p].second|suf[left][s].second)){
ans[i]=min(ans[i],pre[righ][p].first+suf[left][s].first);
p--;
}
else{
s++;
}
}
ans[i]=min(ans[i],min(ans[left],ans[righ]));
}
void pnod(int i,int l,int r){
cout<<"***********************"<<endl;
cout<<"Node ID: "<<i<<endl;
cout<<"Node Range: ["<<l<<','<<r<<']'<<endl;
cout<<"Node len: "<<len[i]<<endl;
cout<<"Node prefixes:"<<endl;
for(auto x:pre[i])cout<<"pre len: "<<x.first<<" pre bitmask "<<x.second<<endl;
cout<<"Node suffixes:"<<endl;
for(auto x:suf[i])cout<<"suf len: "<<x.first<<" suf bitmask "<<x.second<<endl;
cout<<"Answer for this node: "<<ans[i]<<endl;
}
void print(int i,int l,int r){
if(l==r){
pnod(i,l,r);
return;
}
print(left,l,mid);
print(righ,mid+1,r);
pnod(i,l,r);
}
int main()
{
IOS
cin>>n>>k>>m;
for(ll i=0;i<n;i++){
cin>>a[i];
a[i]--;
}
build(0,0,n-1);
//print(0,0,n-1);
while(m--){
ll t;
cin>>t;
if(t==1){
ll p,val;
cin>>p>>val;
p--;val--;
a[p]=val;
upd(0,0,n-1,p);
}
else{
if(ans[0]==inf)cout<<-1<<endl;
else cout<<ans[0]<<endl;
}
}
return 0;
}
Compilation message
nekameleoni.cpp: In function 'void build(long long int, long long int, long long int)':
nekameleoni.cpp:57:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | while(p>=0&&s<suf[left].size()){
| ~^~~~~~~~~~~~~~~~~
nekameleoni.cpp: In function 'void upd(long long int, long long int, long long int, long long int)':
nekameleoni.cpp:104:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while(p>=0&&s<suf[left].size()){
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
20480 KB |
Output is correct |
| 2 |
Correct |
24 ms |
20352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
21248 KB |
Output is correct |
| 2 |
Correct |
35 ms |
21140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
21624 KB |
Output is correct |
| 2 |
Correct |
45 ms |
21632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
377 ms |
29688 KB |
Output is correct |
| 2 |
Correct |
930 ms |
55824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
649 ms |
44920 KB |
Output is correct |
| 2 |
Correct |
994 ms |
63808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
793 ms |
40332 KB |
Output is correct |
| 2 |
Correct |
999 ms |
59788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
978 ms |
51908 KB |
Output is correct |
| 2 |
Correct |
1018 ms |
60936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
986 ms |
48352 KB |
Output is correct |
| 2 |
Correct |
1218 ms |
62604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1338 ms |
66656 KB |
Output is correct |
| 2 |
Correct |
1208 ms |
65700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1167 ms |
66860 KB |
Output is correct |
| 2 |
Correct |
1012 ms |
65656 KB |
Output is correct |
