oj.uz

답안 #51135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -