Submission #1188169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188169		DobromirAngelov	코끼리 (Dancing Elephants) (IOI11_elephants)	C++20	100 / 100	5263 ms	23368 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;

const int MAXN=150005;
const int B=400;
const int INF=(int)1e9+5;

int n;
int L;
int a[MAXN];
int blCnt;
int block[MAXN/B+5][2*B+5];
int cnt[MAXN/B+5];
int dp[MAXN/B+5][2*B+5];
int jump[MAXN/B+5][2*B+5];
pair<int,int> tmp[MAXN];
pair<int,int> tmp2[MAXN];
map<int,int> cntX;

int qrNum=0;
void calcBlock(int ind)
{
    int ptr=cnt[ind]-1;
    dp[ind][cnt[ind]]=0;
    for(int i=cnt[ind]-1;i>=0;i--)
    {
        while(block[ind][ptr]-block[ind][i]>L) ptr--;
        dp[ind][i]=dp[ind][ptr+1]+1;
        if(ptr+1<cnt[ind]) jump[ind][i]=jump[ind][ptr+1];
        else jump[ind][i]=block[ind][i]+L+1;
        if(jump[ind][i]<=block[ind][i]) cout<<"ggg"<<endl;
        if(jump[ind][i]<=block[ind][cnt[ind]-1]) {cout<<"bbb"<<endl; cout<<1/0<<endl;}
    }
    /*if(qrNum==17500)
    {
        cout<<ind<<endl;
        for(int i=0;i<cnt[ind];i++) cout<<block[ind][i]<<" "; cout<<endl;
        //for(int i=0;i<cnt[ind];i++) cout<<a[block[ind][i]]<<" "; cout<<endl;
        for(int i=0;i<cnt[ind];i++) cout<<dp[ind][i]<<" "; cout<<endl;
        for(int i=0;i<cnt[ind];i++) cout<<jump[ind][i]<<" "; cout<<endl;
    }*/
}

void rebuild()
{
    for(int i=0;i<n;i++)
    {
        tmp[i]={a[i],i};
    }
    sort(tmp,tmp+n);
    int ptr=1;
    tmp2[0]=tmp[0];
    for(int i=1;i<n;i++)
    {
        if(tmp[i].fi==tmp[i-1].fi) continue;
        tmp2[ptr++]=tmp[i];
    }
    for(int i=0;i<blCnt;i++)
    {
        cnt[i]=0;
        for(int j=i*B;j<min(ptr,(i+1)*B);j++)
        {
            block[i][j-i*B]=tmp2[j].fi;
            cnt[i]=j-i*B+1;
        }
    }
    for(int i=0;i<blCnt;i++) calcBlock(i);
}

void init(int N, int _L, int X[])
{
    n=N;
    L=_L;
    for(int i=0;i<n;i++) a[i]=X[i];
    blCnt=(n+B-1)/B;

    for(int i=0;i<n;i++) cntX[a[i]]++;

    rebuild();
}

void rem(int ind)
{
    int x=a[ind];
    int curBl=0;
    for(int i=0;i<blCnt;i++)
    {
        if(cnt[i]==0) continue;
        if(block[i][0]<=x && x<=block[i][cnt[i]-1])
        {
            curBl=i;
            break;
        }
    }
    bool fl=0;
    for(int i=0;i<cnt[curBl]-1;i++)
    {
        if(block[curBl][i]==x) fl=1;
        if(fl) block[curBl][i]=block[curBl][i+1];
    }
    cnt[curBl]--;
    calcBlock(curBl);
}

int l[MAXN/B+5];
int r[MAXN/B+5];
void add(int ind,int x)
{
    l[0]=0;
    for(int i=1;i<blCnt;i++)
    {
        l[i]=l[i-1];
        if(cnt[i-1]>0) l[i]=block[i-1][cnt[i-1]-1];
    }
    r[blCnt-1]=INF;
    for(int i=blCnt-2;i>=0;i--)
    {
        r[i]=r[i+1];
        if(cnt[i+1]>0) r[i]=block[i+1][0];
    }

    int curBl=0;
    for(int i=0;i<blCnt;i++)
    {
        if(l[i]<=x && x<=r[i])
        {
            curBl=i;
            break;
        }
    }
    int st=cnt[curBl];
    for(int i=0;i<cnt[curBl];i++)
    {
        if(x<block[curBl][i])
        {
            st=i;
            break;
        }
    }
    for(int i=cnt[curBl];i>st;i--)
    {
        block[curBl][i]=block[curBl][i-1];
    }
    block[curBl][st]=a[ind];
    cnt[curBl]++;
    //if(qrNum==17500){cout<<curBl<<" "<<cnt[curBl]<<" "<<ind<<" "<<st<<endl;
    //for(int i=0;i<10;i++) cout<<cnt[i]<<" "; cout<<endl;}
    calcBlock(curBl);
}

int bs(int ind,int x)
{
    int l=0,r=cnt[ind]-1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(block[ind][mid]<x) l=mid+1;
        else r=mid;
    }
    return l;
}

int getAns()
{
    int ptr=0;
    int x=0;
    int ret=0;
    int lastp=-1, lasti=-1;
    while(1)
    {
        while(ptr<blCnt)
        {
            if(cnt[ptr]==0)
            {
                ptr++;
                continue;
            }
            if(block[ptr][cnt[ptr]-1]<x)
            {
                ptr++;
                continue;
            }
            break;
        }
        if(ptr>=blCnt) break;
        //if(cnt[ptr]==0) cout<<1/0<<endl;
        int ind=bs(ptr,x);
        //if(lastp==ptr && lasti==ind) cout<<1/0<<endl;
        //lastp=ptr; lasti=ind;
        ret+=dp[ptr][ind];
        //if(ptr<0 || ptr>=blCnt || block[ptr][cnt[ptr]-1]<0 || block[ptr][cnt[ptr]-1]>=n) cout<<1/0<<endl;
        //if(jump[ptr][ind]<=a[block[ptr][cnt[ptr]-1]] || qrNum==17500) 
        //{cout<<qrNum<<endl<<ptr<<" "<<x<<" "<<cnt[ptr]<<" "<<ind<<" "<<jump[ptr][ind]<<" "<<block[ptr][cnt[ptr]-1]<<" "<<a[block[ptr][cnt[ptr]-1]]<<" "<<dp[ptr][ind]<<endl; cout<<1/0<<endl;}
        
        x=jump[ptr][ind];//ptr++;
    }
    return ret;
}

int update(int i, int y)
{
    qrNum++;
    cntX[a[i]]--;
    if(cntX[a[i]]==0) rem(i);
    cntX[y]++;
    a[i]=y;
    //if(qrNum==17500) cout<<i<<" "<<y<<endl;
    if(cntX[y]==1) add(i,y);
    if(qrNum%B==0) rebuild();
    return getAns();
}

Compilation message (stderr)

elephants.cpp: In function 'void calcBlock(int)':
elephants.cpp:36:77: warning: division by zero [-Wdiv-by-zero]
   36 |         if(jump[ind][i]<=block[ind][cnt[ind]-1]) {cout<<"bbb"<<endl; cout<<1/0<<endl;}
      |                                                                            ~^~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3