oj.uz

Submission #99619

# Submission time Handle Problem Language Result Execution time Memory
99619 2019-03-05T18:03:11 Z naoai Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 14348 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

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

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 384 KB Output is correct
3 Correct 2 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 384 KB Output is correct
3 Correct 2 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 384 KB Output is correct
3 Correct 2 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 317 ms 1500 KB Output is correct
8 Correct 340 ms 1664 KB Output is correct
9 Correct 639 ms 3048 KB Output is correct
10 Correct 634 ms 3064 KB Output is correct
11 Correct 530 ms 3064 KB Output is correct
12 Correct 885 ms 3148 KB Output is correct
13 Correct 722 ms 4216 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 384 KB Output is correct
3 Correct 2 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 317 ms 1500 KB Output is correct
8 Correct 340 ms 1664 KB Output is correct
9 Correct 639 ms 3048 KB Output is correct
10 Correct 634 ms 3064 KB Output is correct
11 Correct 530 ms 3064 KB Output is correct
12 Correct 885 ms 3148 KB Output is correct
13 Correct 722 ms 4216 KB Output is correct
14 Correct 344 ms 3448 KB Output is correct
15 Correct 594 ms 3704 KB Output is correct
16 Correct 1440 ms 5124 KB Output is correct
17 Correct 1831 ms 6520 KB Output is correct
18 Correct 1840 ms 6264 KB Output is correct
19 Correct 1374 ms 6264 KB Output is correct
20 Correct 1733 ms 6520 KB Output is correct
21 Correct 1584 ms 6416 KB Output is correct
22 Correct 1363 ms 5768 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 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 317 ms 1500 KB Output is correct
8 Correct 340 ms 1664 KB Output is correct
9 Correct 639 ms 3048 KB Output is correct
10 Correct 634 ms 3064 KB Output is correct
11 Correct 530 ms 3064 KB Output is correct
12 Correct 885 ms 3148 KB Output is correct
13 Correct 722 ms 4216 KB Output is correct
14 Correct 344 ms 3448 KB Output is correct
15 Correct 594 ms 3704 KB Output is correct
16 Correct 1440 ms 5124 KB Output is correct
17 Correct 1831 ms 6520 KB Output is correct
18 Correct 1840 ms 6264 KB Output is correct
19 Correct 1374 ms 6264 KB Output is correct
20 Correct 1733 ms 6520 KB Output is correct
21 Correct 1584 ms 6416 KB Output is correct
22 Correct 1363 ms 5768 KB Output is correct
23 Correct 7416 ms 13404 KB Output is correct
24 Correct 7719 ms 13428 KB Output is correct
25 Correct 7339 ms 13400 KB Output is correct
26 Correct 7554 ms 13464 KB Output is correct
27 Correct 6603 ms 13240 KB Output is correct
28 Correct 1435 ms 5420 KB Output is correct
29 Correct 1325 ms 5368 KB Output is correct
30 Correct 1411 ms 5300 KB Output is correct
31 Correct 1348 ms 5388 KB Output is correct
32 Correct 4972 ms 12852 KB Output is correct
33 Correct 3647 ms 12168 KB Output is correct
34 Correct 6904 ms 13120 KB Output is correct
35 Correct 3354 ms 13416 KB Output is correct
36 Correct 1691 ms 12920 KB Output is correct
37 Execution timed out 9036 ms 14348 KB Time limit exceeded
38 Halted 0 ms 0 KB -