Submission #1274813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274813		JeanBombeur	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	10 ms	1408 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
#define all(a) (a).begin(), (a).end()
using namespace std;

const int N = 15e4;
const int SZ = 300;

vector <int> pos[3 * N / SZ];
vector <pair <int, int>> dp[3 * N / SZ];
int to_date[3 * N / SZ];

int x[N];

int length, nb_blocks;

void compute(int id) {
    int sz = (int)size(pos[id]);
    dp[id].resize(sz);
    int nxt_id = id;
    while (nxt_id < nb_blocks - 1 && pos[nxt_id + 1][0] <= pos[id].back() + length)
        nxt_id ++;
    for (int nxt = (int)size(pos[nxt_id]) - 1, i = sz - 1; ~i; i --) {
        while (pos[nxt_id][nxt] > pos[id][i] + length)
            if (!(nxt --))
                nxt = size(pos[-- nxt_id]) - 1;
        dp[id][i] = (nxt_id > id || nxt == sz - 1) ? make_pair(1, nxt_id * N + nxt) : make_pair(1 + dp[id][nxt + 1].first, dp[id][nxt + 1].second);
    }
    to_date[id] = 1;
    return;
}

void reset(int id) {
    for (int i = id - 1; ~i && pos[i].back() >= pos[id][0] - length; i --)
        to_date[i] = 0;
    return;
}

void upd(int v, bool add) {
    int id = 0;
    while (id < nb_blocks - 1 && pos[id].back() < v)
        id ++;
    if (add) {
        pos[id].insert(lower_bound(all(pos[id]), v), v);
        reset(id);
    }
    else {
        reset(id);
        pos[id].erase(lower_bound(all(pos[id]), v));
    }
    if (pos[id].size() == 2 * SZ) {
        for (int i = nb_blocks ++; i > id + 1; i --) {
            swap(pos[i], pos[i - 1]);
            swap(dp[i], dp[i - 1]);
            swap(to_date[i], to_date[i - 1]);
        }
        pos[id + 1].insert(pos[id + 1].begin(), pos[id].begin() + SZ, pos[id].end());
        pos[id].erase(pos[id].begin() + SZ, pos[id].end());
        compute(id + 1);
    }
    if (pos[id].empty()) {
        -- nb_blocks;
        for (int i = id; i < nb_blocks; i ++) {
            swap(pos[i], pos[i + 1]);
            swap(dp[i], dp[i + 1]);
            swap(to_date[i], to_date[i + 1]);
        }
    }
    else
        compute(id);
    return;
}

int answer() {
    int ans = 0, id = 0, i = 0;
    while (id < nb_blocks) {
        if (!to_date[id])
            compute(id);
        ans += dp[id][i].first;
        int jmp = dp[id][i].second;
        id = jmp / N, i = jmp % N;
        if (++ i == (int)size(pos[id]))
            ++ id, i = 0;
    }
    return ans;
}

void init(int N, int L, int X[]) {
    length = L;
    nb_blocks = (SZ - 1 + N) / SZ;
    for (int i = 0; i < N; i ++)
        pos[i / SZ].push_back(x[i] = X[i]);
    for (int i = 0; i < nb_blocks; i ++)
        compute(i);
    return;
}

int update(int id, int nv) {
    upd(x[id], 0);
    upd(x[id] = nv, 1);
    return answer();
}

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