oj.uz

Submission #51140

# Submission time Handle Problem Language Result Execution time Memory
51140 2018-06-16T16:18:00 Z imeimi2000 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 60688 KB 
#include "elephants.h"
#include <algorithm>
#include <map>

using namespace std;

const int t = 2000;
const int MAXN = 2e5;
int n, l, a[MAXN];
int x[MAXN];
int bs;
map<int, int> mp;

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; t * i < n; ++i) {
        bs = i + 1;
        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;
    for (int i = 0; i < n; ++i) ++mp[a[i] = x[i] = X[i]];
    n = unique(x, x + n) - x;
    reset();
}

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

int update(int p, int y) {
    int s, si;
    if (--mp[a[p]] == 0) {
        s = getBuc(a[p]);
        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);
    }
    if (mp[y]++ == 0) {
        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 2 ms 412 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 2 ms 412 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 512 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 2 ms 412 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1568 ms 4256 KB Output is correct
8 Correct 1643 ms 4844 KB Output is correct
9 Correct 1236 ms 5832 KB Output is correct
10 Correct 1237 ms 7464 KB Output is correct
11 Correct 987 ms 7464 KB Output is correct
12 Correct 2289 ms 7464 KB Output is correct
13 Correct 1119 ms 7464 KB Output is correct

Subtask #4
47.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 2 ms 412 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1568 ms 4256 KB Output is correct
8 Correct 1643 ms 4844 KB Output is correct
9 Correct 1236 ms 5832 KB Output is correct
10 Correct 1237 ms 7464 KB Output is correct
11 Correct 987 ms 7464 KB Output is correct
12 Correct 2289 ms 7464 KB Output is correct
13 Correct 1119 ms 7464 KB Output is correct
14 Correct 638 ms 7464 KB Output is correct
15 Correct 2043 ms 7620 KB Output is correct
16 Correct 3218 ms 11172 KB Output is correct
17 Correct 3122 ms 15160 KB Output is correct
18 Correct 3411 ms 17144 KB Output is correct
19 Correct 1709 ms 19644 KB Output is correct
20 Correct 3530 ms 21536 KB Output is correct
21 Correct 3342 ms 23596 KB Output is correct
22 Correct 1524 ms 24920 KB Output is correct

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 2 ms 412 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1568 ms 4256 KB Output is correct
8 Correct 1643 ms 4844 KB Output is correct
9 Correct 1236 ms 5832 KB Output is correct
10 Correct 1237 ms 7464 KB Output is correct
11 Correct 987 ms 7464 KB Output is correct
12 Correct 2289 ms 7464 KB Output is correct
13 Correct 1119 ms 7464 KB Output is correct
14 Correct 638 ms 7464 KB Output is correct
15 Correct 2043 ms 7620 KB Output is correct
16 Correct 3218 ms 11172 KB Output is correct
17 Correct 3122 ms 15160 KB Output is correct
18 Correct 3411 ms 17144 KB Output is correct
19 Correct 1709 ms 19644 KB Output is correct
20 Correct 3530 ms 21536 KB Output is correct
21 Correct 3342 ms 23596 KB Output is correct
22 Correct 1524 ms 24920 KB Output is correct
23 Correct 5034 ms 38136 KB Output is correct
24 Correct 4479 ms 42600 KB Output is correct
25 Correct 3909 ms 46516 KB Output is correct
26 Correct 6569 ms 55888 KB Output is correct
27 Correct 6456 ms 60688 KB Output is correct
28 Execution timed out 9068 ms 60688 KB Time limit exceeded
29 Halted 0 ms 0 KB -