oj.uz

Submission #542513

# Submission time Handle Problem Language Result Execution time Memory
542513 2022-03-26T19:49:09 Z tabr Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 12704 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];
pair<int, int> pos[MAX_N];
int jump_cnt[MAX_N];
int jump_pos[MAX_N];
vector<int> e[MAX_B];

void init(int n_, int l_, int x_[]) {
    n = n_;
    l = l_;
    B = (int) sqrt(n_);
    for (int i = 0; i < n; i++) {
        x[i] = x_[i];
    }
}

void build_one(int id) {
    for (int i = 0; i < (int) e[id].size(); i++) {
        pos[e[id][i]] = make_pair(id, i);
    }
    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() {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        return make_pair(x[i], i) < make_pair(x[j], 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].first].erase(e[pos[i].first].begin() + pos[i].second);
    build_one(pos[i].first);
    // add x[i]
    x[i] = y;
    for (int id = 0; id < B; id++) {
        if (id == B - 1 || x[e[id + 1][0]] > y) {
            x[150001] = y;
            auto iter = lower_bound(e[id].begin(), e[id].end(), 150001, [&](int j, int k) {
                return x[j] < x[k];
            });
            e[id].insert(iter, 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 428 ms 1340 KB Output is correct
8 Correct 494 ms 1484 KB Output is correct
9 Correct 799 ms 2532 KB Output is correct
10 Correct 1006 ms 2528 KB Output is correct
11 Correct 1063 ms 2532 KB Output is correct
12 Correct 1644 ms 2540 KB Output is correct
13 Correct 1094 ms 2532 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 428 ms 1340 KB Output is correct
8 Correct 494 ms 1484 KB Output is correct
9 Correct 799 ms 2532 KB Output is correct
10 Correct 1006 ms 2528 KB Output is correct
11 Correct 1063 ms 2532 KB Output is correct
12 Correct 1644 ms 2540 KB Output is correct
13 Correct 1094 ms 2532 KB Output is correct
14 Correct 997 ms 1860 KB Output is correct
15 Correct 854 ms 1996 KB Output is correct
16 Correct 2344 ms 2772 KB Output is correct
17 Correct 2686 ms 3748 KB Output is correct
18 Correct 2882 ms 3624 KB Output is correct
19 Correct 1691 ms 3636 KB Output is correct
20 Correct 2657 ms 3744 KB Output is correct
21 Correct 2674 ms 3648 KB Output is correct
22 Correct 1739 ms 3628 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 428 ms 1340 KB Output is correct
8 Correct 494 ms 1484 KB Output is correct
9 Correct 799 ms 2532 KB Output is correct
10 Correct 1006 ms 2528 KB Output is correct
11 Correct 1063 ms 2532 KB Output is correct
12 Correct 1644 ms 2540 KB Output is correct
13 Correct 1094 ms 2532 KB Output is correct
14 Correct 997 ms 1860 KB Output is correct
15 Correct 854 ms 1996 KB Output is correct
16 Correct 2344 ms 2772 KB Output is correct
17 Correct 2686 ms 3748 KB Output is correct
18 Correct 2882 ms 3624 KB Output is correct
19 Correct 1691 ms 3636 KB Output is correct
20 Correct 2657 ms 3744 KB Output is correct
21 Correct 2674 ms 3648 KB Output is correct
22 Correct 1739 ms 3628 KB Output is correct
23 Correct 4691 ms 6984 KB Output is correct
24 Correct 5067 ms 6980 KB Output is correct
25 Correct 4148 ms 6984 KB Output is correct
26 Correct 5999 ms 6940 KB Output is correct
27 Correct 6251 ms 6988 KB Output is correct
28 Correct 1365 ms 5316 KB Output is correct
29 Correct 1355 ms 5208 KB Output is correct
30 Correct 1387 ms 5200 KB Output is correct
31 Correct 1339 ms 5204 KB Output is correct
32 Correct 5936 ms 11444 KB Output is correct
33 Correct 5470 ms 10780 KB Output is correct
34 Correct 5507 ms 11656 KB Output is correct
35 Correct 5706 ms 11956 KB Output is correct
36 Correct 4994 ms 11432 KB Output is correct
37 Correct 8925 ms 12704 KB Output is correct
38 Correct 6083 ms 10660 KB Output is correct
39 Correct 5490 ms 11692 KB Output is correct
40 Correct 6035 ms 10700 KB Output is correct
41 Execution timed out 9036 ms 11436 KB Time limit exceeded
42 Halted 0 ms 0 KB -