제출 #1259941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259941		lambd47	Dancing Elephants (IOI11_elephants)	C++20	100 / 100	3192 ms	7488 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;

#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

const int sqr=400;

int tam[sqr];
struct node{
    int x,vai,resp;
};
node dp[sqr][2*sqr];
vector<int> vec;
int m;
int n;
void updbl(int bloco){
    auto &d=dp[bloco];
    R(i,tam[bloco]-1,0){//mudar pra 2pointer
        if(d[tam[bloco]-1].x<=d[i].x+m){
            d[i].vai=d[i].x+m;
            d[i].resp=1;
        }
        else{
            int r=tam[bloco]-1;
            int l=i+1;
            int vai=i;
            while(l<=r){
                int mid=(l+r)/2;
                if(d[mid].x<=d[i].x+m){
                    vai=mid;
                    l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
            vai++;
            d[i].vai=d[vai].vai;
            d[i].resp=d[vai].resp;
            d[i].resp++;
        }
    }
}
void bota(int id,int pos,int bloco){
    R(i,tam[bloco]-1,pos)dp[bloco][i+1]=dp[bloco][i];
    tam[bloco]++;
    dp[bloco][pos].x=id;
    updbl(bloco);
}
void tira(int pos, int bloco){
    L(i,pos,tam[bloco]-1)dp[bloco][i]=dp[bloco][i+1];
    tam[bloco]--;
    updbl(bloco);
}

pair<int,int> find(int val){
    int l=0;
    int r=sqr-1;
    int blocat=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(tam[mid]==0 || dp[mid][0].x>val){
            r=mid-1;
        }
        else{
            blocat=mid;
            l=mid+1;
        }
    }
    l=0;
    r=tam[blocat]-1;
    int ret=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(dp[blocat][mid].x<=val){
            ret=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return {blocat,ret};

}
int calc(){
    int idat=0;
    int bloc=0;
    int resp=0;
    while(true){
        int vai=dp[bloc][idat].vai;
        resp+=dp[bloc][idat].resp;
        bloc++;
        while(bloc<sqr){
            if(tam[bloc]==0)return resp;
            if(dp[bloc][tam[bloc]-1].x>vai)break;
            bloc++;
        }

        int l=0;
        int r=tam[bloc]-1;
        int nid=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(dp[bloc][mid].x<=vai){
                l=mid+1;
                nid=mid;
            }else{
                r=mid-1;
            }
        }
        nid++;
        idat=nid;
        //resp++;
    }
}

void ini(){
    int pat=0;
    L(i,0,sqr-1){
        L(j,0,tam[i]-1){
            vec[pat++]=dp[i][j].x;
        }
        tam[i]=0;
    }
    L(i,0,n-1){
        dp[i/sqr][i%sqr].x=vec[i];
        tam[i/sqr]++;
    }
    L(i,0,sqr-1)updbl(i);
}

vector<int> arr;
void init(int N, int M, int X[])
{
    n=N;m=M;
    vec.resize(n);
    L(i,0,n-1)vec[i]=X[i];
    arr=vec;
    sort(all(vec));
    L(i,0,n-1){
        dp[i/sqr][i%sqr].x=vec[i];
        tam[i/sqr]++;
    }
    L(i,0,sqr-1){
        updbl(i);
    }
}


int cnt=0;
int update(int i, int y)
{
    auto [bl,id]=find(arr[i]);
    arr[i]=y;
    tira(id,bl);
    auto [bl2,id2]=find(arr[i]);
    bota(arr[i],id2+1,bl2);
    //L(i,0,4)cout<<dp[0][i].x<<" ";
    //cout<<"\n";

    cnt++;
    if(cnt==sqr-4){
        ini();
        cnt=0;
    }
    return calc();
}

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