Submission #100712

#	Time	Username	Problem	Language	Result	Execution time	Memory
100712		alexpetrescu	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	9096 ms	5716 KiB

elephants

#include "elephants.h"
#include <vector>
#include <cmath>
#include <algorithm>

#define MAXN 150000
#define MAXR 400

bool seen;
int n, l, k, r;
std::vector < int > v[MAXR];
int u[MAXN], p[MAXN], poz[MAXN];
struct myc {
    int x, y;
} dp[MAXN];

inline int urm(int x) {
    int rez = 0;
    for (int pas = 1 << 8; pas; pas >>= 1)
        if (rez + pas < r && u[v[rez + pas][0]] <= x)
            rez += pas;
    int poz = 0;
    for (int pas = 1 << 9; pas; pas >>= 1)
        if (poz + pas < (int)v[rez].size() && u[v[rez][poz + pas]] <= x)
            poz += pas;
    if (poz + 1 == (int)v[rez].size()) {
        if (rez + 1 == r)
            return -1;
        return v[rez + 1][0];
    }
    return v[rez][poz + 1];
}

inline void calc(std::vector < int > t) {
    for (int i = t.size() - 1; i >= 0; i--) {
        if (u[t[i]] + l >= u[t.back()]) dp[t[i]] = {1, u[t[i]] + l};
        else {
            int x = urm(u[t[i]] + l);
            dp[t[i]] = {1 + dp[x].x, dp[x].y};
        }
    }
}

void init(int N, int L, int X[]) {
    if (seen == 0) {
        n = N;
        l = L;
        k = sqrt(n);
        seen = 1;
        for (int i = 0; i < n; i++)
            p[i] = i;
        for (int i = 0; i < n; i++)
            u[i] = X[i];
    }
    r = 1 + (n - 1) / k;
    for (int i = 0; i < r; i++) {
        v[i].resize(std::min(n, (i + 1) * k) - i * k);
        for (int j = i * k; j < n && j < (i + 1) * k; j++)
            v[i][j - i * k] = p[j], poz[p[j]] = i;
    }
    for (int i = r - 1; i >= 0; i--)
        calc(v[i]);
}

inline void myInit() {
    int aici[1] = {0};
    int j = 0;
    for (int i = 0; i < r; i++)
        for (auto &x : v[i])
            p[j++] = x;
    init(0, 0, aici);
}

inline void scoate(int p) {
    int i = 0;
    while (v[poz[p]][i] != p)
        i++;
    while (i + 1 < (int)v[poz[p]].size()) {
        v[poz[p]][i] = v[poz[p]][i + 1];
        i++;
    }
    v[poz[p]].pop_back();
}

inline void baga(int p) {
    int i = 0;
    while (i < (int)v[poz[p]].size() && u[v[poz[p]][i]] < u[p])
        i++;
    v[poz[p]].push_back(0);
    for (int j = v[poz[p]].size() - 1; j > i; j--)
        v[poz[p]][j] = v[poz[p]][j - 1];
    v[poz[p]][i] = p;
}

int update(int i, int y) {
    int e = 0, f = poz[i];
    for (int pas = 1 << 8; pas; pas >>= 1)
        if (e + pas < r && u[v[e + pas][0]] <= y)
            e += pas;

    scoate(i);
    poz[i] = e;
    u[i] = y;
    baga(i);

    if (f == e)
        calc(v[e]);
    else if (((int)v[f].size() == 0 && f != r - 1) || (int)v[e].size() == 2 * r)
        myInit();
    else if (e < f) {
        if ((int)v[f].size() == 0)
            r--;
        else
            calc(v[f]);
        calc(v[e]);
    } else {
        calc(v[e]);
        calc(v[f]);
    }

    int x = v[0][0], ans = 0;
    while (x != -1) {
        ans += dp[x].x;
        x = urm(dp[x].y);
    }
    return ans;
}

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