Submission #101837

#	Time	Username	Problem	Language	Result	Execution time	Memory
101837		alexpetrescu	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	9065 ms	7204 KiB

elephants

#include "elephants.h"
#include <vector>
#include <algorithm>
 
#define MAXN 150000
#define MAXR 110
#define LOGR 6
#define MAXK 1400
#define LOGK 11
 
bool seen;
int n, l, k, r, mareleCnt;
std::vector < int > v[MAXR];
int u[MAXN], p[MAXN], poz[MAXN];
struct myc {
    int x, y;
} dp[MAXN];
 
inline void calc(std::vector < int > &t) {
    int j = t.size() - 1;
    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 {
            while (j - 1 > i && u[t[j - 1]] > u[t[i]] + l)
                j--;
            dp[t[i]] = {1 + dp[t[j]].x, dp[t[j]].y};
        }
    }
}
 
void init(int N, int L, int X[]) {
    if (seen == 0) {
        n = N;
        l = L;
        k = MAXK;
        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 << LOGR; 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);
 
    mareleCnt++;
    if (mareleCnt % k == 0)
        myInit();
    else 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 val = -1, ans = 0;
    for (int i = 0; i < r; i++) {
        if (val < u[v[i].back()]) {
            int rez = -1;
            for (int pas = 1 << LOGK; pas; pas >>= 1)
                if (rez + pas < (int)v[i].size() && u[v[i][rez + pas]] <= val)
                    rez += pas;
            rez++;
            ans += dp[v[i][rez]].x;
            val = dp[v[i][rez]].y;
        }
    }
    return ans;
}

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