oj.uz

Submission #101833

# Submission time Handle Problem Language Result Execution time Memory
101833 2019-03-20T12:31:57 Z alexpetrescu Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 11920 KB 
#include "elephants.h"
#include <vector>
#include <cmath>
#include <algorithm>

#define MAXN 150000
#define MAXR 100
#define LOGR 6
#define MAXK 1500
#define LOGK 11

bool seen;
int n, l, k, r, mareleCnt;
std::vector < int > v[MAXR];
int u[MAXN], p[MAXN], poz[MAXN];
struct myc {
    int x, y;
} dp[MAXN];

inline void calc(std::vector < int > t) {
    int j = t.size() - 1;
    for (int i = t.size() - 1; i >= 0; i--) {
        if (u[t[i]] + l >= u[t.back()]) dp[t[i]] = {1, u[t[i]] + l};
        else {
            while (j - 1 > i && u[t[j - 1]] > u[t[i]] + l)
                j--;
            dp[t[i]] = {1 + dp[t[j]].x, dp[t[j]].y};
        }
    }
}

void init(int N, int L, int X[]) {
    if (seen == 0) {
        n = N;
        l = L;
        k = MAXK;
        seen = 1;
        for (int i = 0; i < n; i++)
            p[i] = i;
        for (int i = 0; i < n; i++)
            u[i] = X[i];
    }
    r = 1 + (n - 1) / k;
    for (int i = 0; i < r; i++) {
        v[i].resize(std::min(n, (i + 1) * k) - i * k);
        for (int j = i * k; j < n && j < (i + 1) * k; j++)
            v[i][j - i * k] = p[j], poz[p[j]] = i;
    }
    for (int i = r - 1; i >= 0; i--)
        calc(v[i]);
}

inline void myInit() {
    int aici[1] = {0};
    int j = 0;
    for (int i = 0; i < r; i++)
        for (auto &x : v[i])
            p[j++] = x;
    init(0, 0, aici);
}

inline void scoate(int p) {
    int i = 0;
    while (v[poz[p]][i] != p)
        i++;
    while (i + 1 < (int)v[poz[p]].size()) {
        v[poz[p]][i] = v[poz[p]][i + 1];
        i++;
    }
    v[poz[p]].pop_back();
}

inline void baga(int p) {
    int i = 0;
    while (i < (int)v[poz[p]].size() && u[v[poz[p]][i]] < u[p])
        i++;
    v[poz[p]].push_back(0);
    for (int j = v[poz[p]].size() - 1; j > i; j--)
        v[poz[p]][j] = v[poz[p]][j - 1];
    v[poz[p]][i] = p;
}

int update(int i, int y) {
    int e = 0, f = poz[i];
    for (int pas = 1 << LOGR; pas; pas >>= 1)
        if (e + pas < r && u[v[e + pas][0]] <= y)
            e += pas;

    scoate(i);
    poz[i] = e;
    u[i] = y;
    baga(i);

    mareleCnt++;
    if (mareleCnt % k == 0)
        myInit();
    else if (f == e)
        calc(v[e]);
    else if (((int)v[f].size() == 0 && f != r - 1) || (int)v[e].size() == 2 * r)
        myInit();
    else if (e < f) {
        if ((int)v[f].size() == 0)
            r--;
        else
            calc(v[f]);
        calc(v[e]);
    } else {
        calc(v[e]);
        calc(v[f]);
    }

    int val = -1, ans = 0;
    for (int i = 0; i < r; i++) {
        if (val < u[v[i].back()]) {
            int rez = -1;
            for (int pas = 1 << LOGK; pas; pas >>= 1)
                if (rez + pas < (int)v[i].size() && u[v[i][rez + pas]] <= val)
                    rez += pas;
            rez++;
            ans += dp[v[i][rez]].x;
            val = dp[v[i][rez]].y;
        }
    }
    return ans;
}

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 3 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 3 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 3 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 708 ms 1328 KB Output is correct
8 Correct 669 ms 1500 KB Output is correct
9 Correct 724 ms 2652 KB Output is correct
10 Correct 765 ms 2380 KB Output is correct
11 Correct 651 ms 2428 KB Output is correct
12 Correct 2114 ms 2556 KB Output is correct
13 Correct 765 ms 2424 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 3 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 708 ms 1328 KB Output is correct
8 Correct 669 ms 1500 KB Output is correct
9 Correct 724 ms 2652 KB Output is correct
10 Correct 765 ms 2380 KB Output is correct
11 Correct 651 ms 2428 KB Output is correct
12 Correct 2114 ms 2556 KB Output is correct
13 Correct 765 ms 2424 KB Output is correct
14 Correct 996 ms 1912 KB Output is correct
15 Correct 1004 ms 2040 KB Output is correct
16 Correct 3629 ms 2852 KB Output is correct
17 Correct 3575 ms 3576 KB Output is correct
18 Correct 3937 ms 3420 KB Output is correct
19 Correct 1461 ms 3316 KB Output is correct
20 Correct 3527 ms 5496 KB Output is correct
21 Correct 3462 ms 5428 KB Output is correct
22 Correct 1442 ms 4728 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 3 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 708 ms 1328 KB Output is correct
8 Correct 669 ms 1500 KB Output is correct
9 Correct 724 ms 2652 KB Output is correct
10 Correct 765 ms 2380 KB Output is correct
11 Correct 651 ms 2428 KB Output is correct
12 Correct 2114 ms 2556 KB Output is correct
13 Correct 765 ms 2424 KB Output is correct
14 Correct 996 ms 1912 KB Output is correct
15 Correct 1004 ms 2040 KB Output is correct
16 Correct 3629 ms 2852 KB Output is correct
17 Correct 3575 ms 3576 KB Output is correct
18 Correct 3937 ms 3420 KB Output is correct
19 Correct 1461 ms 3316 KB Output is correct
20 Correct 3527 ms 5496 KB Output is correct
21 Correct 3462 ms 5428 KB Output is correct
22 Correct 1442 ms 4728 KB Output is correct
23 Correct 4458 ms 11568 KB Output is correct
24 Correct 4541 ms 11824 KB Output is correct
25 Correct 3438 ms 11708 KB Output is correct
26 Correct 7012 ms 11332 KB Output is correct
27 Correct 6943 ms 11168 KB Output is correct
28 Correct 5366 ms 5340 KB Output is correct
29 Correct 5217 ms 5260 KB Output is correct
30 Correct 5243 ms 5288 KB Output is correct
31 Correct 5136 ms 5368 KB Output is correct
32 Correct 4661 ms 10744 KB Output is correct
33 Correct 2811 ms 10232 KB Output is correct
34 Correct 4282 ms 11000 KB Output is correct
35 Correct 2625 ms 11256 KB Output is correct
36 Correct 3113 ms 10740 KB Output is correct
37 Correct 8544 ms 11920 KB Output is correct
38 Correct 4675 ms 9988 KB Output is correct
39 Correct 4383 ms 11084 KB Output is correct
40 Correct 5278 ms 9976 KB Output is correct
41 Execution timed out 9091 ms 11356 KB Time limit exceeded
42 Halted 0 ms 0 KB -