Submission #1188129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188129		DobromirAngelov	Dancing Elephants (IOI11_elephants)	C++20	50 / 100	774 ms	8092 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;

void calcBlock(int ind)
{
    int ptr=cnt[ind]-1;
    dp[ind][cnt[ind]]=0;
    for(int i=cnt[ind]-1;i>=0;i--)
    {
        while(a[block[ind][ptr]]-a[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]=a[block[ind][i]]+L+1;
    }
}

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++)
    {
        for(int j=i*B;j<min(ptr,(i+1)*B);j++)
        {
            block[i][j-i*B]=tmp2[j].se;
            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(a[block[i][0]]<=x && x<=a[block[i][cnt[i]-1]])
        {
            curBl=i;
            break;
        }
    }
    bool fl=0;
    for(int i=0;i<cnt[curBl];i++)
    {
        if(a[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)
{
    a[ind]=x;
    l[0]=0;
    for(int i=1;i<blCnt;i++)
    {
        l[i]=l[i-1];
        if(cnt[i-1]>0) l[i]=a[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]=a[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<a[block[curBl][i]])
        {
            st=i;
            break;
        }
    }
    for(int i=cnt[curBl];i>st;i--)
    {
        block[curBl][i]=block[curBl][i-1];
    }
    block[curBl][st]=ind;
    cnt[curBl]++;
    calcBlock(curBl);
}

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

int getAns()
{
    int ptr=0;
    int x=0;
    int ret=0;
    while(1)
    {
        while(ptr<blCnt)
        {
            if(cnt[ptr]==0)
            {
                ptr++;
                continue;
            }
            if(a[block[ptr][cnt[ptr]-1]]<x)
            {
                ptr++;
                continue;
            }
            break;
        }
        if(ptr>=blCnt) break;
        int ind=bs(ptr,x);
        ret+=dp[ptr][ind];
        x=jump[ptr][ind];
    }
    return ret;
}

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

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