oj.uz

Submission #51136

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

using namespace std;

const int t = 2000;
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 5 ms 468 KB Output is correct
3 Correct 2 ms 544 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 5 ms 468 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 3 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 628 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 5 ms 468 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 3 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 1482 ms 1528 KB Output is correct
8 Correct 1517 ms 1664 KB Output is correct
9 Correct 1170 ms 2560 KB Output is correct
10 Correct 1109 ms 2632 KB Output is correct
11 Correct 1131 ms 2632 KB Output is correct
12 Correct 2093 ms 2796 KB Output is correct
13 Correct 1051 ms 2796 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 5 ms 468 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 3 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 1482 ms 1528 KB Output is correct
8 Correct 1517 ms 1664 KB Output is correct
9 Correct 1170 ms 2560 KB Output is correct
10 Correct 1109 ms 2632 KB Output is correct
11 Correct 1131 ms 2632 KB Output is correct
12 Correct 2093 ms 2796 KB Output is correct
13 Correct 1051 ms 2796 KB Output is correct
14 Incorrect 457 ms 2796 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 5 ms 468 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 3 ms 544 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 1482 ms 1528 KB Output is correct
8 Correct 1517 ms 1664 KB Output is correct
9 Correct 1170 ms 2560 KB Output is correct
10 Correct 1109 ms 2632 KB Output is correct
11 Correct 1131 ms 2632 KB Output is correct
12 Correct 2093 ms 2796 KB Output is correct
13 Correct 1051 ms 2796 KB Output is correct
14 Incorrect 457 ms 2796 KB Output isn't correct
15 Halted 0 ms 0 KB -