Submission #1184492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184492		GGOSHAB	Dancing Elephants (IOI11_elephants)	C++20	26 / 100	18 ms	1348 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"

#define all(v) begin(v), end(v)

using namespace std;

int n, l;

const int inf = 1e9 + 10;
const int maxn = 2e5 + 5;
int pos[maxn];

struct block {
    int n = 0;
    vector<int> x = {}, last = {}, dp = {};
    block() {};
    void rebuild() {
        x.push_back(inf);
        last.assign(n + 1, -1);
        dp.assign(n + 1, 0);
        int j = n;
        for (int i = n - 1; i >= 0; --i) {
            while (j > 0 && x[i] + l < x[j - 1]) j--;
            last[i] = (j == n ? i : last[j]);
            dp[i] = dp[j] + 1;
        }
        x.pop_back();
        last.pop_back();
        dp.pop_back();
    }
    void insert(int y) {
        auto it = lower_bound(all(x), y);
        x.insert(it, y);
        n++;
        rebuild();
    }
    void erase(int y) {
        auto it = lower_bound(all(x), y);
        x.erase(it);
        n--;
        rebuild();
    }
};

const int B = 400;
block b[B];

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    for (int i = 0; i < n; ++i) {
        pos[i] = X[i];
        b[i / B].insert(pos[i]);
    }
}

int it = 0;
int update(int i, int y) {
    int bl = 0;
    for (bl = 0; bl < B; ++bl) {
        if (b[bl].x.empty()) {
            bl--;
            break;
        }
        if (b[bl].x.back() >= pos[i]) {
            break;
        }
    }
    bl = max(bl, 0);
    b[bl].erase(pos[i]);
    pos[i] = y;
    for (bl = 0; bl < B; ++bl) {
        if (b[bl].x.empty()) {
            bl--;
            break;
        }
        if (b[bl].x.back() >= pos[i]) {
            break;
        }
    }
    bl = max(bl, 0);
    b[bl].insert(pos[i]);

    int res = 0, last = -inf;
    for (int bl = 0; bl < B; ++bl) {
        if (b[bl].n == 0) break;
        int i = upper_bound(all(b[bl].x), last + l) - b[bl].x.begin();
        if (i >= b[bl].n) continue;
        res += b[bl].dp[i];
        last = b[bl].last[i];
    }

    if (it++ > B) {
        for (int i = 0; i < B; ++i) {
            b[i] = {};
        }
        vector<int> p(n);
        iota(all(p), 0);
        sort(all(p), [](int i, int j) { return pos[i] < pos[j]; });
        for (int i = 0; i < n; ++i) {
            b[i / B].insert(pos[p[i]]);
        }
        it = 0;
    }

    return res;
}

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