Submission #1205376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205376		Hamed_Ghaffari	Dancing Elephants (IOI11_elephants)	C++20	100 / 100	5867 ms	7584 KiB

elephants

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

using pii = pair<int, int>;

#define ff first
#define ss second

const int MXN = 15e4+5, sq = 400, sqi = MXN/sq+5;

int n, L, X[MXN], szx[sqi], arr[sqi][sq<<1], xs[MXN], num, dp[sqi][sq<<1], wh[sqi][sq<<1];
pii lim[sqi];

inline pii gx(int i) { return pii(X[i], i); }

inline void rebuild(int t) {
    int r=szx[t]-1;
    for(int l=szx[t]-1; l>=0; l--) {
        while(X[arr[t][l]]+L<X[arr[t][r]]) r--;
        if(r+1<szx[t]) {
            dp[t][l] = dp[t][r+1] + 1;
            wh[t][l] = wh[t][r+1];
        }
        else {
            dp[t][l] = 1;
            wh[t][l] = X[arr[t][l]]+L+1;
        }
    }
}

inline void build(bool fix_xs=1) {
    if(fix_xs) {
        int ptr=0;
        for(int t=0; t<num; t++) {
            for(int i=0; i<szx[t]; i++)
                xs[ptr++] = arr[t][i];
            szx[t] = 0;
        }
        num = 0;
    }
    for(int i=0; i<n; i+=sq) {
        for(int j=i; j<i+sq && j<n; j++)
            arr[num][szx[num]++] = xs[j],
            lim[num] = {X[xs[j]], xs[j]};
        rebuild(num++);
    }
    lim[num-1] = {1e9, 1e9};
}

inline void erase(int i) {
    for(int t=0; t<num; t++)
        if(gx(i)<=lim[t]) {
            for(int j=0; j<szx[t]; j++)
                if(arr[t][j]==i) {
                    for(int k=j+1; k<szx[t]; k++)
                        arr[t][k-1] = arr[t][k];
                    szx[t]--;
                    break;
                }
            rebuild(t);
            break;
        }
}

inline void insert(int i) {
    for(int t=0; t<num; t++)
        if(gx(i)<=lim[t]) {
            arr[t][szx[t]++] = i;
            for(int j=szx[t]-1; j>0 && gx(arr[t][j])<gx(arr[t][j-1]); j--)
                swap(arr[t][j], arr[t][j-1]);
            rebuild(t);
            break;
        }
}

void init(int N, int L, int X[]) {
    n = N;
    ::L = L;
    for(int i=0; i<n; i++) ::X[i] = X[i], xs[i] = i;
    build(0);
}

int cnt;

int update(int i, int y) {
    erase(i);
    X[i] = y;
    insert(i);
    if((++cnt)==sq) {
        build();
        cnt = 0;
    }

    int cur=0, ans=0;
    for(int t=0, l, r, mid; t<num; t++) {
        l=-1, r=szx[t], mid;
        while(r-l>1) {
            mid = l+r>>1;
            (X[arr[t][mid]]>=cur ? r : l) = mid;
        }
        if(r<szx[t]) {
            ans += dp[t][r];
            cur = wh[t][r];
        }
    }

    return ans;
}

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