Submission #272124

#	Time	Username	Problem	Language	Result	Execution time	Memory
272124		mayhoubsaleh	Nekameleoni (COCI15_nekameleoni)	C++14	140 / 140	1338 ms	66860 KiB

nekameleoni

#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 (stderr)

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()){
      |                 ~^~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14