oj.uz

Submission #99620

# Submission time Handle Problem Language Result Execution time Memory
99620 2019-03-05T18:10:46 Z naoai Dancing Elephants (IOI11_elephants) C++14
100 / 100
 6885 ms 12164 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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