oj.uz

Submission #100712

# Submission time Handle Problem Language Result Execution time Memory
100712 2019-03-13T15:10:24 Z alexpetrescu Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 5716 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]] <= 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.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
16.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 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #3
24.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 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 954 ms 1400 KB Output is correct
8 Correct 1253 ms 2476 KB Output is correct
9 Correct 2819 ms 4232 KB Output is correct
10 Correct 3249 ms 3704 KB Output is correct
11 Correct 1937 ms 3632 KB Output is correct
12 Correct 4404 ms 4120 KB Output is correct
13 Correct 3542 ms 3508 KB Output is correct

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 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 954 ms 1400 KB Output is correct
8 Correct 1253 ms 2476 KB Output is correct
9 Correct 2819 ms 4232 KB Output is correct
10 Correct 3249 ms 3704 KB Output is correct
11 Correct 1937 ms 3632 KB Output is correct
12 Correct 4404 ms 4120 KB Output is correct
13 Correct 3542 ms 3508 KB Output is correct
14 Correct 1924 ms 3480 KB Output is correct
15 Correct 2226 ms 3468 KB Output is correct
16 Correct 5449 ms 4720 KB Output is correct
17 Correct 7843 ms 5716 KB Output is correct
18 Correct 8598 ms 5652 KB Output is correct
19 Execution timed out 9096 ms 5240 KB Time limit exceeded
20 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 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 954 ms 1400 KB Output is correct
8 Correct 1253 ms 2476 KB Output is correct
9 Correct 2819 ms 4232 KB Output is correct
10 Correct 3249 ms 3704 KB Output is correct
11 Correct 1937 ms 3632 KB Output is correct
12 Correct 4404 ms 4120 KB Output is correct
13 Correct 3542 ms 3508 KB Output is correct
14 Correct 1924 ms 3480 KB Output is correct
15 Correct 2226 ms 3468 KB Output is correct
16 Correct 5449 ms 4720 KB Output is correct
17 Correct 7843 ms 5716 KB Output is correct
18 Correct 8598 ms 5652 KB Output is correct
19 Execution timed out 9096 ms 5240 KB Time limit exceeded
20 Halted 0 ms 0 KB -