oj.uz

Submission #542466

# Submission time Handle Problem Language Result Execution time Memory
542466 2022-03-26T18:36:09 Z tabr Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 7076 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

const int MAX_N = 150015;
const int MAX_B = 810;
int B;
int n;
int l;
int upd_cnt;
int x[MAX_N];
int pos[MAX_N];
int jump_cnt[MAX_N];
int jump_pos[MAX_N];
int e[MAX_B][MAX_B];
int sz[MAX_B];
int order[MAX_N];

void init(int n_, int l_, int x_[]) {
    n = n_;
    l = l_;
    B = (int) sqrt(n_ * (n <= 1000 ? 1 : 0.8));
    for (int i = 0; i < n; i++) {
        x[i] = x_[i];
    }
    iota(order, order + n, 0);
}

void build_one(int id) {
    sort(e[id], e[id] + sz[id], [&](int i, int j) {
        return x[i] < x[j];
    });
    for (int i = 0; i < sz[id]; i++) {
        pos[e[id][i]] = id;
    }
    for (int i = sz[id] - 1, j = sz[id]; i >= 0; i--) {
        while (j > 0 && x[e[id][j - 1]] > x[e[id][i]] + l) {
            j--;
        }
        if (j == sz[id]) {
            jump_cnt[e[id][i]] = 1;
            jump_pos[e[id][i]] = x[e[id][i]] + l + 1;
        } else {
            jump_cnt[e[id][i]] = jump_cnt[e[id][j]] + 1;
            jump_pos[e[id][i]] = jump_pos[e[id][j]];
        }
    }
}

void build() {
    sort(order, order + n, [&](int i, int j) {
        return x[i] < x[j];
    });
    for (int i = 0; i < B; i++) {
        sz[i] = 0;
        for (int j = n * i / B; j < n * (i + 1) / B; j++) {
            e[i][sz[i]] = order[j];
            sz[i]++;
        }
        build_one(i);
    }
}

int update(int i, int y) {
    if (n == 1) {
        return 1;
    }
    if (upd_cnt == 0) {
        build();
    }
    upd_cnt++;
    if (upd_cnt == n / B - 1) {
        upd_cnt = 0;
    }
    // remove x[i]
    for (int j = 0; j < sz[pos[i]] - 1; j++) {
        if (e[pos[i]][j] == i) {
            e[pos[i]][j] = e[pos[i]][sz[pos[i]] - 1];
            break;
        }
    }
    sz[pos[i]]--;
    build_one(pos[i]);
    // add x[i]
    x[i] = y;
    for (int id = 0; id < B; id++) {
        if (id == B - 1 || x[e[id + 1][0]] > y) {
            e[id][sz[id]] = i;
            sz[id]++;
            build_one(id);
            break;
        }
    }
    // answer
    int ans = 0;
    int now = 0;
    for (int id = 0; id < B; id++) {
        x[150001] = now;
        auto iter = lower_bound(e[id], e[id] + sz[id], 150001, [&](int j, int k) {
            return x[j] < x[k];
        });
        if (iter == e[id] + sz[id]) {
            continue;
        }
        ans += jump_cnt[*iter];
        now = jump_pos[*iter];
    }
    return ans;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n_ = 4;
    int l_ = 10;
    int x_[10];
    x_[0] = 10;
    x_[1] = 15;
    x_[2] = 17;
    x_[3] = 20;
    init(n_, l_, x_);
    debug(update(2, 16));  // 1
    debug(update(1, 25));  // 2
    debug(update(3, 35));  // 2
    debug(update(0, 38));  // 2
    debug(update(2, 0));   // 3
    return 0;
}
#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 550 ms 2188 KB Output is correct
8 Correct 711 ms 2480 KB Output is correct
9 Correct 1078 ms 3516 KB Output is correct
10 Correct 1628 ms 3504 KB Output is correct
11 Correct 1617 ms 3528 KB Output is correct
12 Correct 1888 ms 3516 KB Output is correct
13 Correct 1656 ms 3524 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 550 ms 2188 KB Output is correct
8 Correct 711 ms 2480 KB Output is correct
9 Correct 1078 ms 3516 KB Output is correct
10 Correct 1628 ms 3504 KB Output is correct
11 Correct 1617 ms 3528 KB Output is correct
12 Correct 1888 ms 3516 KB Output is correct
13 Correct 1656 ms 3524 KB Output is correct
14 Correct 913 ms 2732 KB Output is correct
15 Correct 1216 ms 3032 KB Output is correct
16 Correct 2367 ms 3480 KB Output is correct
17 Correct 3041 ms 4072 KB Output is correct
18 Correct 3300 ms 3936 KB Output is correct
19 Correct 3558 ms 3936 KB Output is correct
20 Correct 3027 ms 4028 KB Output is correct
21 Correct 3333 ms 3940 KB Output is correct
22 Correct 2972 ms 3936 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 550 ms 2188 KB Output is correct
8 Correct 711 ms 2480 KB Output is correct
9 Correct 1078 ms 3516 KB Output is correct
10 Correct 1628 ms 3504 KB Output is correct
11 Correct 1617 ms 3528 KB Output is correct
12 Correct 1888 ms 3516 KB Output is correct
13 Correct 1656 ms 3524 KB Output is correct
14 Correct 913 ms 2732 KB Output is correct
15 Correct 1216 ms 3032 KB Output is correct
16 Correct 2367 ms 3480 KB Output is correct
17 Correct 3041 ms 4072 KB Output is correct
18 Correct 3300 ms 3936 KB Output is correct
19 Correct 3558 ms 3936 KB Output is correct
20 Correct 3027 ms 4028 KB Output is correct
21 Correct 3333 ms 3940 KB Output is correct
22 Correct 2972 ms 3936 KB Output is correct
23 Correct 6699 ms 7076 KB Output is correct
24 Correct 6957 ms 7072 KB Output is correct
25 Correct 6474 ms 7072 KB Output is correct
26 Execution timed out 9084 ms 6924 KB Time limit exceeded
27 Halted 0 ms 0 KB -