Submission #745545

#	Time	Username	Problem	Language	Result	Execution time	Memory
745545		bgnbvnbv	Nekameleoni (COCI15_nekameleoni)	C++14	140 / 140	1901 ms	326132 KiB

nekameleoni

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

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;
      |            ~^~

• 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