oj.uz

Submission #99616

# Submission time Handle Problem Language Result Execution time Memory
99616 2019-03-05T17:23:33 Z naoai Dancing Elephants (IOI11_elephants) C++14
26 / 100
 655 ms 2564 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][rad + 1];

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;
    }

    assert(idx == n);
    for (int i = 0; i < n - 1; ++ i)
        assert(pozitii[i].first <= pozitii[i + 1].first);

    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 (v[i][sz[i] - 1].x <= posst)
            continue;

        assert(2 * n2 > sz[i]);

        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;
        assert(v[i][pos].x > posst);
        total += v[i][pos].dp;
        posst = v[i][pos].pos;
    }

    return total;
}

int update(int I, int y) {
    ++ up_cnt;
    if (up_cnt == rad) {
        refa_bucketuri();
        up_cnt = 0;
    }

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

    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
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 328 ms 1388 KB Output is correct
8 Correct 359 ms 1544 KB Output is correct
9 Correct 655 ms 2564 KB Output is correct
10 Incorrect 35 ms 2532 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
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 328 ms 1388 KB Output is correct
8 Correct 359 ms 1544 KB Output is correct
9 Correct 655 ms 2564 KB Output is correct
10 Incorrect 35 ms 2532 KB Output isn't correct
11 Halted 0 ms 0 KB -

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 328 ms 1388 KB Output is correct
8 Correct 359 ms 1544 KB Output is correct
9 Correct 655 ms 2564 KB Output is correct
10 Incorrect 35 ms 2532 KB Output isn't correct
11 Halted 0 ms 0 KB -