답안 #56440 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56440	2018-07-11T10:36:52 Z	aquablitz11	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	8405 ms	125152 KB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;

const int N = 150010;
const int SN = 390;

int n, sn, l, X[N];
vector<int> elep[SN], cnt[N], rbnd[N];

int find_bucket(int x)
{
    for (int i = 0; i < sn; ++i) {
        if (!elep[i].empty() && x <= elep[i].back())
            return i;
    }
    return sn-1;
}

void process_bucket(int p)
{
    //fprintf(stderr, "process_bucket(%d):\n", p);
    int n = elep[p].size();
    cnt[p].resize(n);
    rbnd[p].resize(n);
    for (int i = n-1, j = n-1; i >= 0; --i) {
        while (elep[p][j]-elep[p][i] > l)
            --j;
        cnt[p][i] = j == n-1 ? 1 : (1 + cnt[p][j+1]);
        rbnd[p][i] = j == n-1 ? (elep[p][i]+l) : rbnd[p][j+1];
    }
    /*for (int i = 0; i < n; ++i) {
        if (i != 0) fprintf(stderr, " ");
        fprintf(stderr, "%3d", elep[p][i]);
    }
    fprintf(stderr, "\n");
    for (int i = 0; i < n; ++i) {
        if (i != 0) fprintf(stderr, " ");
        fprintf(stderr, "%3d", cnt[p][i]);
    }
    fprintf(stderr, "\n");
    for (int i = 0; i < n; ++i) {
        if (i != 0) fprintf(stderr, " ");
        fprintf(stderr, "%3d", rbnd[p][i]);
    }
    fprintf(stderr, "\n");
    fprintf(stderr, "\n");*/
}

void process_all()
{
    //fprintf(stderr, "process_all():\n");
    vector<int> X(::X, ::X+n);
    sort(X.begin(), X.end());
    for (int i = 0; i < sn; ++i) {
        elep[i].clear();
        elep[i].reserve(3*sn);
    }
    for (int i = 0; i < n; ++i) {
        int b = i/sn;
        if (b >= sn) b = sn-1;
        elep[b].push_back(X[i]);
        //fprintf(stderr, "add elephant X = %d to block %d\n", X[i], b);
    }
    //fprintf(stderr, "\n");
    for (int i = 0; i < sn; ++i)
        process_bucket(i);
}

void init(int n, int l, int X[])
{
    ::n = n, ::l = l, ::sn = sqrt(n);
    for (int i = 0; i < n; ++i)
        ::X[i] = X[i];
    process_all();
}

int cnt_upd = 0;
bool force = false;
bool skip = false;
int update(int i, int y)
{
    //fprintf(stderr, "update(%d, %d):\n", i, y);
    if (force || (!skip && ((++cnt_upd) % sn == 0))) {
        X[i] = y;
        process_all();
    } else {
        int bx = find_bucket(X[i]);
        int by = find_bucket(y);
        elep[bx].erase(find(elep[bx].begin(), elep[bx].end(), X[i]));
        elep[by].insert(lower_bound(elep[by].begin(), elep[by].end(), y), y);
        //fprintf(stderr, "%d is in bucket %d, %d is in bucket %d\n", X[i], bx, y, by);
        process_bucket(bx);
        if (bx != by) process_bucket(by);
        X[i] = y;
    }
    //fprintf(stderr, "\n");

    int ans = 0, last = -1;
    for (int b = 0; b < sn; ++b) {
        int i = upper_bound(elep[b].begin(), elep[b].end(), last) - elep[b].begin();
        if (i < elep[b].size()) {
            //fprintf(stderr, "block %d, got elephant %d: %d %d %d\n", b, i, elep[b][i], cnt[b][i], rbnd[b][i]);
            ans += cnt[b][i];
            last = rbnd[b][i];
        }
    }

    return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:102:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < elep[b].size()) {
             ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7416 KB	Output is correct
2	Correct	9 ms	7524 KB	Output is correct
3	Correct	9 ms	7524 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7416 KB	Output is correct
2	Correct	9 ms	7524 KB	Output is correct
3	Correct	9 ms	7524 KB	Output is correct
4	Correct	10 ms	7524 KB	Output is correct
5	Correct	9 ms	7524 KB	Output is correct
6	Correct	15 ms	7560 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7416 KB	Output is correct
2	Correct	9 ms	7524 KB	Output is correct
3	Correct	9 ms	7524 KB	Output is correct
4	Correct	10 ms	7524 KB	Output is correct
5	Correct	9 ms	7524 KB	Output is correct
6	Correct	15 ms	7560 KB	Output is correct
7	Correct	357 ms	8712 KB	Output is correct
8	Correct	438 ms	9864 KB	Output is correct
9	Correct	700 ms	12728 KB	Output is correct
10	Correct	1219 ms	13896 KB	Output is correct
11	Correct	1221 ms	15160 KB	Output is correct
12	Correct	1490 ms	16908 KB	Output is correct
13	Correct	1033 ms	17732 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7416 KB	Output is correct
2	Correct	9 ms	7524 KB	Output is correct
3	Correct	9 ms	7524 KB	Output is correct
4	Correct	10 ms	7524 KB	Output is correct
5	Correct	9 ms	7524 KB	Output is correct
6	Correct	15 ms	7560 KB	Output is correct
7	Correct	357 ms	8712 KB	Output is correct
8	Correct	438 ms	9864 KB	Output is correct
9	Correct	700 ms	12728 KB	Output is correct
10	Correct	1219 ms	13896 KB	Output is correct
11	Correct	1221 ms	15160 KB	Output is correct
12	Correct	1490 ms	16908 KB	Output is correct
13	Correct	1033 ms	17732 KB	Output is correct
14	Correct	774 ms	18616 KB	Output is correct
15	Correct	676 ms	20280 KB	Output is correct
16	Correct	2070 ms	23204 KB	Output is correct
17	Correct	2702 ms	25888 KB	Output is correct
18	Correct	2828 ms	27876 KB	Output is correct
19	Correct	1765 ms	29448 KB	Output is correct
20	Correct	2557 ms	32144 KB	Output is correct
21	Correct	2302 ms	34316 KB	Output is correct
22	Correct	2061 ms	35160 KB	Output is correct

Subtask #5
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7416 KB	Output is correct
2	Correct	9 ms	7524 KB	Output is correct
3	Correct	9 ms	7524 KB	Output is correct
4	Correct	10 ms	7524 KB	Output is correct
5	Correct	9 ms	7524 KB	Output is correct
6	Correct	15 ms	7560 KB	Output is correct
7	Correct	357 ms	8712 KB	Output is correct
8	Correct	438 ms	9864 KB	Output is correct
9	Correct	700 ms	12728 KB	Output is correct
10	Correct	1219 ms	13896 KB	Output is correct
11	Correct	1221 ms	15160 KB	Output is correct
12	Correct	1490 ms	16908 KB	Output is correct
13	Correct	1033 ms	17732 KB	Output is correct
14	Correct	774 ms	18616 KB	Output is correct
15	Correct	676 ms	20280 KB	Output is correct
16	Correct	2070 ms	23204 KB	Output is correct
17	Correct	2702 ms	25888 KB	Output is correct
18	Correct	2828 ms	27876 KB	Output is correct
19	Correct	1765 ms	29448 KB	Output is correct
20	Correct	2557 ms	32144 KB	Output is correct
21	Correct	2302 ms	34316 KB	Output is correct
22	Correct	2061 ms	35160 KB	Output is correct
23	Correct	4581 ms	44480 KB	Output is correct
24	Correct	4359 ms	49620 KB	Output is correct
25	Correct	3940 ms	54224 KB	Output is correct
26	Correct	5365 ms	58724 KB	Output is correct
27	Correct	6324 ms	63600 KB	Output is correct
28	Correct	1261 ms	63600 KB	Output is correct
29	Correct	1252 ms	65060 KB	Output is correct
30	Correct	1275 ms	67976 KB	Output is correct
31	Correct	1197 ms	70912 KB	Output is correct
32	Correct	6412 ms	79840 KB	Output is correct
33	Correct	6268 ms	83600 KB	Output is correct
34	Correct	6034 ms	88408 KB	Output is correct
35	Correct	4701 ms	94664 KB	Output is correct
36	Correct	3318 ms	97760 KB	Output is correct
37	Correct	7790 ms	103840 KB	Output is correct
38	Correct	6548 ms	106268 KB	Output is correct
39	Correct	5486 ms	111052 KB	Output is correct
40	Correct	6190 ms	114668 KB	Output is correct
41	Correct	8246 ms	120352 KB	Output is correct
42	Correct	8405 ms	125152 KB	Output is correct

답안 #56440

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