답안 #51141 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51141	2018-06-16T16:19:38 Z	imeimi2000	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	3127 ms	78636 KB

elephants

#include "elephants.h"
#include <algorithm>
#include <map>

using namespace std;

const int t = 500;
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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	432 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	2 ms	432 KB	Output is correct
4	Correct	2 ms	448 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	684 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	2 ms	432 KB	Output is correct
4	Correct	2 ms	448 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	684 KB	Output is correct
7	Correct	295 ms	4372 KB	Output is correct
8	Correct	321 ms	4836 KB	Output is correct
9	Correct	444 ms	6156 KB	Output is correct
10	Correct	500 ms	7636 KB	Output is correct
11	Correct	501 ms	7672 KB	Output is correct
12	Correct	805 ms	7812 KB	Output is correct
13	Correct	444 ms	7812 KB	Output is correct

Subtask #4
47.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	2 ms	432 KB	Output is correct
4	Correct	2 ms	448 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	684 KB	Output is correct
7	Correct	295 ms	4372 KB	Output is correct
8	Correct	321 ms	4836 KB	Output is correct
9	Correct	444 ms	6156 KB	Output is correct
10	Correct	500 ms	7636 KB	Output is correct
11	Correct	501 ms	7672 KB	Output is correct
12	Correct	805 ms	7812 KB	Output is correct
13	Correct	444 ms	7812 KB	Output is correct
14	Correct	249 ms	7812 KB	Output is correct
15	Correct	483 ms	7812 KB	Output is correct
16	Correct	1052 ms	8500 KB	Output is correct
17	Correct	1080 ms	10236 KB	Output is correct
18	Correct	1268 ms	10380 KB	Output is correct
19	Correct	793 ms	10736 KB	Output is correct
20	Correct	1224 ms	10736 KB	Output is correct
21	Correct	1105 ms	10736 KB	Output is correct
22	Correct	742 ms	10736 KB	Output is correct

Subtask #5
3.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	2 ms	432 KB	Output is correct
4	Correct	2 ms	448 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	684 KB	Output is correct
7	Correct	295 ms	4372 KB	Output is correct
8	Correct	321 ms	4836 KB	Output is correct
9	Correct	444 ms	6156 KB	Output is correct
10	Correct	500 ms	7636 KB	Output is correct
11	Correct	501 ms	7672 KB	Output is correct
12	Correct	805 ms	7812 KB	Output is correct
13	Correct	444 ms	7812 KB	Output is correct
14	Correct	249 ms	7812 KB	Output is correct
15	Correct	483 ms	7812 KB	Output is correct
16	Correct	1052 ms	8500 KB	Output is correct
17	Correct	1080 ms	10236 KB	Output is correct
18	Correct	1268 ms	10380 KB	Output is correct
19	Correct	793 ms	10736 KB	Output is correct
20	Correct	1224 ms	10736 KB	Output is correct
21	Correct	1105 ms	10736 KB	Output is correct
22	Correct	742 ms	10736 KB	Output is correct
23	Correct	2497 ms	19208 KB	Output is correct
24	Correct	2521 ms	19208 KB	Output is correct
25	Correct	1788 ms	19208 KB	Output is correct
26	Correct	2128 ms	21948 KB	Output is correct
27	Correct	2635 ms	21960 KB	Output is correct
28	Correct	2588 ms	21960 KB	Output is correct
29	Correct	2335 ms	21960 KB	Output is correct
30	Correct	2650 ms	21960 KB	Output is correct
31	Correct	2380 ms	21960 KB	Output is correct
32	Correct	2888 ms	35304 KB	Output is correct
33	Correct	1401 ms	35304 KB	Output is correct
34	Correct	2738 ms	43840 KB	Output is correct
35	Correct	871 ms	43840 KB	Output is correct
36	Correct	83 ms	43840 KB	Output is correct
37	Correct	1460 ms	50900 KB	Output is correct
38	Correct	2502 ms	61816 KB	Output is correct
39	Correct	2372 ms	66452 KB	Output is correct
40	Correct	2514 ms	70088 KB	Output is correct
41	Correct	3087 ms	73800 KB	Output is correct
42	Correct	3127 ms	78636 KB	Output is correct

답안 #51141

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 47.0 / 47.0

Subtask #5 3.0 / 3.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
47.0 / 47.0

Subtask #5
3.0 / 3.0