Submission #1273363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273363		JeanBombeur	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9090 ms	2844 KiB

elephants

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include "elephants.h"
using namespace std;

const int INF = 1e9 + 1;
const int N = 15e4;
const int SQRT = 600;

int pos[N];

vector <int> bucket[SQRT];
int toDate[SQRT];

vector <pair <int, int>> jump[SQRT];

int nbElephants, length;

void build_bucket(int id) {
    int sz = size(bucket[id]);
    jump[id].resize(sz);
    int nxt = 0, nxtId = id;
    
    while (!bucket[nxtId].empty() && bucket[nxtId][0] <= bucket[id].back() + length)
        nxtId ++;
    nxtId --;
    
    while (nxt < (int)size(bucket[nxtId]) && bucket[nxtId][nxt] <= bucket[id].back() + length)
        nxt ++;
    nxt --;
    
    for (int i = sz - 1; i >= 0; i --)
    {
        while (bucket[nxtId][nxt] > bucket[id][i] + length)
            if (!(nxt --))
                nxt = size(bucket[-- nxtId]) - 1;
        
        if (nxtId > id || nxt == sz - 1)
            jump[id][i] = {1, nxtId * 2 * SQRT + nxt};
        else
            jump[id][i] = {1 + jump[id][nxt + 1].first, jump[id][nxt + 1].second};
    }
    toDate[id] = 1;
    return;
}

void update_bucket(int id) {
    int cur = id - 1;
    while (cur >= 0 && bucket[cur].back() + length >= bucket[id][0])
        toDate[cur --] = 0;
    return;
}

void insert(int id, int val) {
    vector <int> nv;
    for (int a : bucket[id])
    {
        if (a >= val)
        {
            nv.push_back(val);
            val = INF;
        }
        nv.push_back(a);
    }
    if (val < INF)
        nv.push_back(val);
    bucket[id] = nv;
    build_bucket(id);
    update_bucket(id);
    return;
}

void remove(int id, int val) {
    vector <int> nv;
    for (int a : bucket[id])
    {
        if (a == val)
            val = -1;
        else
            nv.push_back(a);
    }
    bucket[id] = nv;
    build_bucket(id);
    update_bucket(id);
    return;
}

int answer() {
    int ans = 0, cur = 0, id = 0;
    while (!bucket[id].empty())
    {
        // if (!toDate[id])
            build_bucket(id);
        ans += jump[id][cur].first;
        int jmp = jump[id][cur].second;
        id = jmp / (2 * SQRT), cur = jmp % (2 * SQRT);
        if (++ cur == (int)size(bucket[id]))
            id ++, cur = 0;
    }
    return ans;
}

void reset_buckets() {
    vector <int> allPos;
    int cur = 0;
    while (!bucket[cur].empty())
    {
        for (int a : bucket[cur])
            allPos.push_back(a);
        bucket[cur ++].clear();
    }
    cur = 0;
    for (int i = 0; i < nbElephants; i ++)
    {
        if ((int)size(bucket[cur]) > SQRT && (nbElephants - i) >= SQRT / 2)
            cur ++;
        bucket[cur].push_back(allPos[i]);
    }
    for (int i = 0; i <= cur; i ++)
        build_bucket(i);
    return;
}

void init(int N, int L, int X[]) {
    nbElephants = N;
    length = L;
    for (int i = 0; i < nbElephants; i ++)
        bucket[0].push_back(pos[i] = X[i]);

    sort(bucket[0].begin(), bucket[0].end());
    reset_buckets();
    return;
}

int find(int val) {
    int cur = 0;
    while (!bucket[cur].empty() && bucket[cur].back() < val)
        cur ++;
    return cur - bucket[cur].empty();
}

int update(int id, int nv) {
    
    int prev = pos[id];
    pos[id] = nv;
    
    bool reset = false;
    
    int cur = find(prev);
    remove(cur, prev);
    reset |= size(bucket[cur]) <= 1;
    
    cur = find(nv);
    insert(cur, nv);
    reset |= size(bucket[cur]) >= 2 * SQRT;
    
    if (reset)
        reset_buckets();
    
    return answer();
}

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