제출 #1188165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188165		DobromirAngelov	코끼리 (Dancing Elephants) (IOI11_elephants)	C++20	50 / 100	674 ms	3024 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=451;
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];

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);
    for(int i=0;i<blCnt;i++)
    {
        for(int j=i*B;j<min(n,(i+1)*B);j++)
        {
            block[i][j-i*B]=tmp[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;

    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]-1;i++)
    {
        if(a[block[curBl][i]]==x) fl=1;
        if(fl) block[curBl][i]=block[curBl][i+1];
    }
    cnt[curBl]--;
    calcBlock(curBl);
}

void add(int ind,int x)
{
    a[ind]=x;

    int curBl=blCnt-1;
    for(int i=0;i<blCnt;i++)
    {
        if(cnt[i]==0) continue;
        if(x<=a[block[i][cnt[i]-1]])
        {
            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++;
    rem(i);
    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