oj.uz

Submission #542458

# Submission time Handle Problem Language Result Execution time Memory
542458 2022-03-26T18:25:48 Z tabr Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 6220 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];
vector<int> e[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 : 1.5));
    for (int i = 0; i < n; i++) {
        x[i] = x_[i];
    }
    for (int i = 0; i < B; i++) {
        e[i].reserve(n / B + 10);
    }
    iota(order, order + n, 0);
}

void build_one(int id) {
    assert(!e[id].empty());
    sort(e[id].begin(), e[id].end(), [&](int i, int j) {
        return x[i] < x[j];
    });
    for (int i = 0; i < (int) e[id].size(); i++) {
        pos[e[id][i]] = id;
    }
    for (int i = (int) e[id].size() - 1, j = (int) e[id].size(); i >= 0; i--) {
        while (j > 0 && x[e[id][j - 1]] > x[e[id][i]] + l) {
            j--;
        }
        if (j == (int) e[id].size()) {
            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++) {
        e[i].clear();
        for (int j = n * i / B; j < n * (i + 1) / B; j++) {
            e[i].emplace_back(order[j]);
        }
        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]
    e[pos[i]].erase(find(e[pos[i]].begin(), e[pos[i]].end(), 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].emplace_back(i);
            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].begin(), e[id].end(), 150001, [&](int j, int k) {
            return x[j] < x[k];
        });
        if (iter == e[id].end()) {
            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 674 ms 1564 KB Output is correct
8 Correct 790 ms 1816 KB Output is correct
9 Correct 1353 ms 2708 KB Output is correct
10 Correct 2282 ms 2712 KB Output is correct
11 Correct 2333 ms 2716 KB Output is correct
12 Correct 2387 ms 2788 KB Output is correct
13 Correct 2417 ms 2712 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 674 ms 1564 KB Output is correct
8 Correct 790 ms 1816 KB Output is correct
9 Correct 1353 ms 2708 KB Output is correct
10 Correct 2282 ms 2712 KB Output is correct
11 Correct 2333 ms 2716 KB Output is correct
12 Correct 2387 ms 2788 KB Output is correct
13 Correct 2417 ms 2712 KB Output is correct
14 Correct 1116 ms 2088 KB Output is correct
15 Correct 1327 ms 2240 KB Output is correct
16 Correct 2957 ms 2560 KB Output is correct
17 Correct 3811 ms 3152 KB Output is correct
18 Correct 4158 ms 3132 KB Output is correct
19 Correct 4846 ms 3104 KB Output is correct
20 Correct 3780 ms 3256 KB Output is correct
21 Correct 4134 ms 3264 KB Output is correct
22 Correct 3994 ms 3108 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 674 ms 1564 KB Output is correct
8 Correct 790 ms 1816 KB Output is correct
9 Correct 1353 ms 2708 KB Output is correct
10 Correct 2282 ms 2712 KB Output is correct
11 Correct 2333 ms 2716 KB Output is correct
12 Correct 2387 ms 2788 KB Output is correct
13 Correct 2417 ms 2712 KB Output is correct
14 Correct 1116 ms 2088 KB Output is correct
15 Correct 1327 ms 2240 KB Output is correct
16 Correct 2957 ms 2560 KB Output is correct
17 Correct 3811 ms 3152 KB Output is correct
18 Correct 4158 ms 3132 KB Output is correct
19 Correct 4846 ms 3104 KB Output is correct
20 Correct 3780 ms 3256 KB Output is correct
21 Correct 4134 ms 3264 KB Output is correct
22 Correct 3994 ms 3108 KB Output is correct
23 Correct 8487 ms 6216 KB Output is correct
24 Correct 8793 ms 6220 KB Output is correct
25 Correct 7614 ms 6220 KB Output is correct
26 Execution timed out 9056 ms 6120 KB Time limit exceeded
27 Halted 0 ms 0 KB -