oj.uz

Submission #51135

# Submission time Handle Problem Language Result Execution time Memory
51135 2018-06-16T09:19:05 Z 강태규(#1289, imeimi2000) Dancing Elephants (IOI11_elephants) C++11
50 / 100
 547 ms 4708 KB 
#include "elephants.h"
#include <algorithm>

using namespace std;

const int t = 400;
const int MAXN = 2e5;
int n, l, a[MAXN];
int x[MAXN];
int bs;

struct _dp {
    int cnt, mx;
    _dp operator+(int x) const {
        return { cnt + x, mx };
    }
} dp[t][t << 1 | 1];

int buc[t][t << 1 | 1];
int s[t];

const int inf = 1e9 + 7;
void recalc(int s) {
    int j = buc[s][0];
    for (int i = j++; i > 0; --i) {
        while (j > 1 && buc[s][i] + l < buc[s][j - 1]) --j;
        if (j <= buc[s][0]) dp[s][i] = dp[s][j] + 1;
        else dp[s][i] = { 1, buc[s][i] };
    }
}

void reset() {
    for (int i = 0; i < bs; ++i) {
        buc[i][0] = 0;
        for (int j = 0; j < t && t * i + j < n; ++j) {
            buc[i][++buc[i][0]] = x[t * i + j];
        }
        recalc(i);
        s[i] = buc[i][1];
    }
}

void getX() {
    int p = 0;
    for (int i = 0; i < bs; ++i) {
        for (int j = 1; j <= buc[i][0]; ++j) {
            x[p++] = buc[i][j];
        }
    }
}

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    bs = (n + t - 1) / t;
    for (int i = 0; i < n; ++i) a[i] = x[i] = X[i];
    reset();
}

int getBuc(int i) {
    return lower_bound(s + 1, s + bs, i + 1) - s - 1;
}

int update(int p, int y) {
    int s = getBuc(a[p]);
    int si = lower_bound(buc[s] + 1, buc[s] + (buc[s][0] + 1), a[p]) - buc[s];
    for (int i = si; i < buc[s][0]; ++i) {
        buc[s][i] = buc[s][i + 1];
    }
    --buc[s][0];
    --n;
    recalc(s);
    s = getBuc(y);
    if (buc[s][0] == (t << 1)) getX(), reset(), s = getBuc(y);
    si = lower_bound(buc[s] + 1, buc[s] + (buc[s][0] + 1), y) - buc[s];
    for (int i = ++buc[s][0]; i > si; --i) {
        buc[s][i] = buc[s][i - 1];
    }
    buc[s][si] = y;
    ++n;
    recalc(s);
    a[p] = y;
    
    int ret = 0;
    p = -inf;
    for (int i = 0; i < bs; ++i) {
        int j = lower_bound(buc[i] + 1, buc[i] + (buc[i][0] + 1), p + l + 1) - buc[i];
        if (j <= buc[i][0]) {
            ret += dp[i][j].cnt;
            p = dp[i][j].mx;
        }
    }
    return ret;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 428 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 608 KB Output is correct
6 Correct 2 ms 608 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 428 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 608 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 235 ms 1708 KB Output is correct
8 Correct 282 ms 1896 KB Output is correct
9 Correct 352 ms 2920 KB Output is correct
10 Correct 374 ms 2920 KB Output is correct
11 Correct 443 ms 3048 KB Output is correct
12 Correct 547 ms 3048 KB Output is correct
13 Correct 368 ms 4092 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 428 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 608 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 235 ms 1708 KB Output is correct
8 Correct 282 ms 1896 KB Output is correct
9 Correct 352 ms 2920 KB Output is correct
10 Correct 374 ms 2920 KB Output is correct
11 Correct 443 ms 3048 KB Output is correct
12 Correct 547 ms 3048 KB Output is correct
13 Correct 368 ms 4092 KB Output is correct
14 Incorrect 108 ms 4708 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 428 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 608 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 235 ms 1708 KB Output is correct
8 Correct 282 ms 1896 KB Output is correct
9 Correct 352 ms 2920 KB Output is correct
10 Correct 374 ms 2920 KB Output is correct
11 Correct 443 ms 3048 KB Output is correct
12 Correct 547 ms 3048 KB Output is correct
13 Correct 368 ms 4092 KB Output is correct
14 Incorrect 108 ms 4708 KB Output isn't correct
15 Halted 0 ms 0 KB -