oj.uz

Submission #101829

# Submission time Handle Problem Language Result Execution time Memory
101829 2019-03-20T12:18:43 Z alexpetrescu Dancing Elephants (IOI11_elephants) C++14
50 / 100
 7916 ms 4192 KB 
#include "elephants.h"
#include <vector>
#include <cmath>
#include <algorithm>

#define MAXN 150000
#define MAXR 150
#define MAXK 1000
#define LOGK 9

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 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 << 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 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.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 434 ms 2148 KB Output is correct
8 Correct 505 ms 2452 KB Output is correct
9 Correct 622 ms 4188 KB Output is correct
10 Correct 784 ms 3804 KB Output is correct
11 Correct 745 ms 3676 KB Output is correct
12 Correct 7916 ms 4192 KB Output is correct
13 Correct 679 ms 3576 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 434 ms 2148 KB Output is correct
8 Correct 505 ms 2452 KB Output is correct
9 Correct 622 ms 4188 KB Output is correct
10 Correct 784 ms 3804 KB Output is correct
11 Correct 745 ms 3676 KB Output is correct
12 Correct 7916 ms 4192 KB Output is correct
13 Correct 679 ms 3576 KB Output is correct
14 Incorrect 52 ms 3200 KB Output isn't correct
15 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 434 ms 2148 KB Output is correct
8 Correct 505 ms 2452 KB Output is correct
9 Correct 622 ms 4188 KB Output is correct
10 Correct 784 ms 3804 KB Output is correct
11 Correct 745 ms 3676 KB Output is correct
12 Correct 7916 ms 4192 KB Output is correct
13 Correct 679 ms 3576 KB Output is correct
14 Incorrect 52 ms 3200 KB Output isn't correct
15 Halted 0 ms 0 KB -