답안 #99620 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99620	2019-03-05T18:10:46 Z	naoai	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	6885 ms	12164 KB

elephants

#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

static const int nmax = 15e4;
static const int rad = 400 * 4;

static int n, L;
static int up_cnt;
static int bucket[nmax + 1];
static pair<int, int> pozitii[nmax + 1];

static int nrb;
static int sz[nmax / rad + 1];

struct str {
    int x, ind, pos, dp;
};

str v[nmax / rad + 1][2 * rad + 5];

void compute (int b) {
    int ind = sz[b];
    for (int i = sz[b] - 1; i >= 0; -- i) {
        while (ind - 1 > i && v[b][ind - 1].x > v[b][i].x + L) {
            -- ind;
        }

        if (ind == sz[b]) {
            v[b][i].dp = 1;
            v[b][i].pos = v[b][i].x + L;
        } else {
            v[b][i].dp = v[b][ind].dp + 1;
            v[b][i].pos = v[b][ind].pos;
        }
    }
}

void refa_bucketuri () {
    int idx = 0;
    for (int b = 0; b < nrb; ++ b) {
        for (int k = 0; k < sz[b]; ++ k) {
            pozitii[idx ++] = {v[b][k].x, v[b][k].ind};
        }

        sz[b] = 0;
    }

    for (int i = 0, b = 0; i < n; i += rad, ++ b) {
        for (int j = i; j < i + rad && j < n; ++ j) {
            v[b][sz[b]].x = pozitii[j].first;
            v[b][sz[b] ++].ind = pozitii[j].second;
            bucket[pozitii[j].second] = b;
        }

        compute(b);
    }
}

void init (int N, int l, int X[]) {
    n = N;
    L = l;

    for (int i = 0; i < n; i += rad, ++ nrb) {
        for (int j = i; j < i + rad && j < n; ++ j) {
            v[nrb][sz[nrb]].x = X[j];
            v[nrb][sz[nrb] ++].ind = j;
        }
    }

    refa_bucketuri();
}

int solve () {
    int total = 0;
    int posst = -1;

    int n2 = 1;
    for (n2 = 1; (n2 << 1) <= 3 * rad; n2 <<= 1) {
    }

    for (int i = 0; i < nrb; ++ i) {
        if (sz[i] == 0) continue;
        if (v[i][sz[i] - 1].x <= posst)
            continue;

        int pos = -1;
        for (int step = n2; step > 0; step >>= 1) {
            if (pos + step < sz[i] && v[i][pos + step].x <= posst)
                pos += step;
        }

        ++ pos;
        total += v[i][pos].dp;
        posst = v[i][pos].pos;
    }

    return total;
}

int update(int I, int y) {
    ++ up_cnt;

    if (up_cnt % rad == 0) {
        refa_bucketuri();
    }

    // sterg i
    int ind = bucket[I], pos = -1;
    for (int i = 0; i < sz[ind]; ++ i)
        if (v[ind][i].ind == I)
            pos = i;

    for (int i = pos; i < sz[ind] - 1; ++ i)
        v[ind][i] = v[ind][i + 1];
    -- sz[ind];
    compute(ind);

    //caut bucket nou
    ind = 0;
    while (ind + 1 < nrb && v[ind + 1][0].x <= y)
        ++ ind;
    pos = 0;
    while (pos < sz[ind] && v[ind][pos].x <= y)
        ++ pos;

    // inserez in ind, pos
    for (int i = sz[ind] - 1; i >= pos; -- i)
        v[ind][i + 1] = v[ind][i];

    v[ind][pos].x = y;
    v[ind][pos].ind = I;

    bucket[I] = ind;
    ++ sz[ind];
    compute(ind);

    return solve();
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	1014 ms	1436 KB	Output is correct
8	Correct	1095 ms	1584 KB	Output is correct
9	Correct	939 ms	2732 KB	Output is correct
10	Correct	642 ms	2684 KB	Output is correct
11	Correct	621 ms	2716 KB	Output is correct
12	Correct	1457 ms	3036 KB	Output is correct
13	Correct	619 ms	2952 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	1014 ms	1436 KB	Output is correct
8	Correct	1095 ms	1584 KB	Output is correct
9	Correct	939 ms	2732 KB	Output is correct
10	Correct	642 ms	2684 KB	Output is correct
11	Correct	621 ms	2716 KB	Output is correct
12	Correct	1457 ms	3036 KB	Output is correct
13	Correct	619 ms	2952 KB	Output is correct
14	Correct	955 ms	2248 KB	Output is correct
15	Correct	1617 ms	2168 KB	Output is correct
16	Correct	2663 ms	3192 KB	Output is correct
17	Correct	2507 ms	3932 KB	Output is correct
18	Correct	2791 ms	3916 KB	Output is correct
19	Correct	1340 ms	3860 KB	Output is correct
20	Correct	2372 ms	4160 KB	Output is correct
21	Correct	2309 ms	3848 KB	Output is correct
22	Correct	1324 ms	3756 KB	Output is correct

Subtask #5
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	1014 ms	1436 KB	Output is correct
8	Correct	1095 ms	1584 KB	Output is correct
9	Correct	939 ms	2732 KB	Output is correct
10	Correct	642 ms	2684 KB	Output is correct
11	Correct	621 ms	2716 KB	Output is correct
12	Correct	1457 ms	3036 KB	Output is correct
13	Correct	619 ms	2952 KB	Output is correct
14	Correct	955 ms	2248 KB	Output is correct
15	Correct	1617 ms	2168 KB	Output is correct
16	Correct	2663 ms	3192 KB	Output is correct
17	Correct	2507 ms	3932 KB	Output is correct
18	Correct	2791 ms	3916 KB	Output is correct
19	Correct	1340 ms	3860 KB	Output is correct
20	Correct	2372 ms	4160 KB	Output is correct
21	Correct	2309 ms	3848 KB	Output is correct
22	Correct	1324 ms	3756 KB	Output is correct
23	Correct	4974 ms	7368 KB	Output is correct
24	Correct	5274 ms	7416 KB	Output is correct
25	Correct	3728 ms	7416 KB	Output is correct
26	Correct	4914 ms	7420 KB	Output is correct
27	Correct	5391 ms	7376 KB	Output is correct
28	Correct	4967 ms	2576 KB	Output is correct
29	Correct	4972 ms	2452 KB	Output is correct
30	Correct	4929 ms	2552 KB	Output is correct
31	Correct	5188 ms	2576 KB	Output is correct
32	Correct	3576 ms	7420 KB	Output is correct
33	Correct	2321 ms	7392 KB	Output is correct
34	Correct	3326 ms	7384 KB	Output is correct
35	Correct	2481 ms	7500 KB	Output is correct
36	Correct	2221 ms	7416 KB	Output is correct
37	Correct	5339 ms	8688 KB	Output is correct
38	Correct	3155 ms	10940 KB	Output is correct
39	Correct	3588 ms	11964 KB	Output is correct
40	Correct	3345 ms	10972 KB	Output is correct
41	Correct	6808 ms	11980 KB	Output is correct
42	Correct	6885 ms	12164 KB	Output is correct

답안 #99620

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