oj.uz

Submission #101835

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

#define MAXN 150000
#define MAXR 100
#define LOGR 6
#define MAXK 1600
#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 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 3 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 3 ms 384 KB Output is correct
7 Correct 697 ms 1752 KB Output is correct
8 Correct 819 ms 1784 KB Output is correct
9 Correct 798 ms 2924 KB Output is correct
10 Correct 737 ms 2852 KB Output is correct
11 Correct 676 ms 2684 KB Output is correct
12 Correct 2074 ms 3224 KB Output is correct
13 Correct 751 ms 2936 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 3 ms 384 KB Output is correct
7 Correct 697 ms 1752 KB Output is correct
8 Correct 819 ms 1784 KB Output is correct
9 Correct 798 ms 2924 KB Output is correct
10 Correct 737 ms 2852 KB Output is correct
11 Correct 676 ms 2684 KB Output is correct
12 Correct 2074 ms 3224 KB Output is correct
13 Correct 751 ms 2936 KB Output is correct
14 Correct 1086 ms 2108 KB Output is correct
15 Correct 1063 ms 2328 KB Output is correct
16 Correct 3767 ms 3192 KB Output is correct
17 Correct 3661 ms 3860 KB Output is correct
18 Correct 3827 ms 3836 KB Output is correct
19 Correct 1507 ms 3448 KB Output is correct
20 Correct 3804 ms 4600 KB Output is correct
21 Correct 3555 ms 4472 KB Output is correct
22 Correct 1519 ms 4776 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 3 ms 384 KB Output is correct
7 Correct 697 ms 1752 KB Output is correct
8 Correct 819 ms 1784 KB Output is correct
9 Correct 798 ms 2924 KB Output is correct
10 Correct 737 ms 2852 KB Output is correct
11 Correct 676 ms 2684 KB Output is correct
12 Correct 2074 ms 3224 KB Output is correct
13 Correct 751 ms 2936 KB Output is correct
14 Correct 1086 ms 2108 KB Output is correct
15 Correct 1063 ms 2328 KB Output is correct
16 Correct 3767 ms 3192 KB Output is correct
17 Correct 3661 ms 3860 KB Output is correct
18 Correct 3827 ms 3836 KB Output is correct
19 Correct 1507 ms 3448 KB Output is correct
20 Correct 3804 ms 4600 KB Output is correct
21 Correct 3555 ms 4472 KB Output is correct
22 Correct 1519 ms 4776 KB Output is correct
23 Correct 4783 ms 7596 KB Output is correct
24 Correct 5018 ms 7800 KB Output is correct
25 Correct 4021 ms 7544 KB Output is correct
26 Correct 5618 ms 7296 KB Output is correct
27 Correct 6547 ms 7292 KB Output is correct
28 Correct 5151 ms 3172 KB Output is correct
29 Correct 5287 ms 3192 KB Output is correct
30 Correct 5425 ms 3192 KB Output is correct
31 Correct 5381 ms 3424 KB Output is correct
32 Correct 4118 ms 7268 KB Output is correct
33 Correct 2586 ms 7288 KB Output is correct
34 Correct 4147 ms 7288 KB Output is correct
35 Correct 2592 ms 7288 KB Output is correct
36 Correct 2989 ms 7328 KB Output is correct
37 Execution timed out 9072 ms 7992 KB Time limit exceeded
38 Halted 0 ms 0 KB -