Submission #559643

#	Time	Username	Problem	Language	Result	Execution time	Memory
559643		ngpin04	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	2599 ms	14556 KiB

elephants

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
const int Nmax = 15e4 + 5;
const int Q = 400;
const int K = 1100;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

#include "elephants.h"
//#include "grader.cpp"

int ptr[Nmax / K][2 * K + 5];
int dp[Nmax / K][2 * K + 5];
int b[Nmax / K][2 * K + 5];
int v[Nmax / K][2 * K + 5];

pair <int, int> pos[Nmax];

int sz[Nmax];
int x[Nmax];
int n,l,cnt,cntb;

void build(int p, int b[], int ptr[], int dp[], int v[]) {
    dp[sz[p]] = 0;
    for (int i = sz[p] - 1, j = sz[p]; i >= 0; i--) {
        while (v[j - 1] - v[i] > l)
            j--;
        if (j == sz[p]) {
            dp[i] = 0;
            ptr[i] = i;
        } else {
            ptr[i] = ptr[j];
            dp[i] = dp[j] + 1;
        }
    }
}

void del(int i) {
    int p = pos[i].fi;
    int ind = pos[i].se;
    for (int j = ind; j + 1 < sz[p]; j++)
        b[p][j] = b[p][j + 1];
    sz[p]--;

    for (int j = 0; j < sz[p]; j++) {
        pos[b[p][j]] = mp(p, j);
        v[p][j] = x[b[p][j]];
    }

    build(p, b[p], ptr[p], dp[p], v[p]);
}

int getmax(int p) {
    return v[p][sz[p] - 1];
}

void add(int i) {
    int p = 0;
    while (p < cntb && (sz[p] > 0 && getmax(p) < x[i]))
        p++;

    int ind = -1;
    while (ind + 1 < sz[p] && v[p][ind + 1] < x[i])
        ind++;

    for (int j = sz[p]; j - 1 > ind; j--)
        b[p][j] = b[p][j - 1];

    b[p][ind + 1] = i;
    sz[p]++;
    for (int j = 0; j < sz[p]; j++) {
        pos[b[p][j]] = mp(p, j);
        v[p][j] = x[b[p][j]];
    }

    build(p, b[p], ptr[p], dp[p], v[p]);
}

void rebuild() {
    vector <int> ind;

    for (int i = 0; i <= cntb; i++) {
        for (int j = 0; j < sz[i]; j++)
            ind.push_back(b[i][j]);
        sz[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int p = i / K;
        int it = ind[i];
        pos[it] = mp(p, sz[p]);
        b[p][sz[p]++] = it;
    }

    for (int i = 0; i <= cntb; i++) {
        for (int j = 0; j < sz[i]; j++) 
            v[i][j] = x[b[i][j]];

        build(i, b[i], ptr[i], dp[i], v[i]);
    }
}

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    for (int i = 0; i < n; i++)
        x[i] = X[i];

    cntb = (n - 1) / K;

    vector <int> ind(n, 0);
    iota(ALL(ind), 0);
    sort(ALL(ind), [](int i, int j) {
        return x[i] < x[j];
    });

    for (int i = 0; i < n; i++) {
        int p = i / K;
        int it = ind[i];
        pos[it] = mp(p, sz[p]);
        b[p][sz[p]++] = it;
    }

    for (int i = 0; i <= cntb; i++) {
        for (int j = 0; j < sz[i]; j++) 
            v[i][j] = x[b[i][j]];

        build(i, b[i], ptr[i], dp[i], v[i]);
    }
}

int update(int i, int y) {
    cnt++;
    del(i);
    x[i] = y;
    add(i);

    int res = 0;
    int p = 0;
    int cur = 0;

    while (true) {
        res += dp[p][cur];
        cur = ptr[p][cur];
        int nxt = p + 1;
        while (nxt <= cntb && 
        (sz[nxt] == 0 || getmax(nxt) - v[p][cur] <= l)) 
            nxt++;

        res++;
        if (nxt > cntb) 
            break;
        
        int lo = -1;
        int hi = sz[nxt] - 1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (v[nxt][mid] - v[p][cur] <= l)
                lo = mid;
            else
                hi = mid;
        }

        cur = hi;
        p = nxt;
    }

    if (cnt == Q) {
        cnt = 0;
        rebuild();
    }
    return res;
}

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