oj.uz

Submission #100708

# Submission time Handle Problem Language Result Execution time Memory
100708 2019-03-13T14:58:53 Z alexpetrescu Dancing Elephants (IOI11_elephants) C++14
10 / 100
 2 ms 384 KB 
#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]] <= u[x] + l)
            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]] <= u[x] + l)
            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--) {
        int x = urm(t[i]);
        if (x == -1 || poz[x] != poz[t[i]]) dp[t[i]] = {1, x};
        else 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 = dp[x].y;
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -