oj.uz

Submission #542454

# Submission time Handle Problem Language Result Execution time Memory
542454 2022-03-26T18:18:14 Z tabr Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 7500 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];
int order[MAX_N];

void init(int n_, int l_, int x_[]) {
    n = n_;
    l = l_;
    B = (int) sqrt(n_ * (n <= 1000 ? 1 : 2));
    for (int i = 0; i < n; i++) {
        x[i] = x_[i];
    }
    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 make_pair(x[i], i) < make_pair(x[j], j);
    });
    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() {
    sort(order, order + n, [&](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) {
            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 372 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 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 0 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 372 KB Output is correct
3 Correct 0 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 734 ms 1364 KB Output is correct
8 Correct 899 ms 1484 KB Output is correct
9 Correct 1530 ms 2640 KB Output is correct
10 Correct 2624 ms 2660 KB Output is correct
11 Correct 2630 ms 2648 KB Output is correct
12 Correct 2812 ms 2640 KB Output is correct
13 Correct 2649 ms 2648 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 372 KB Output is correct
3 Correct 0 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 734 ms 1364 KB Output is correct
8 Correct 899 ms 1484 KB Output is correct
9 Correct 1530 ms 2640 KB Output is correct
10 Correct 2624 ms 2660 KB Output is correct
11 Correct 2630 ms 2648 KB Output is correct
12 Correct 2812 ms 2640 KB Output is correct
13 Correct 2649 ms 2648 KB Output is correct
14 Correct 1760 ms 2032 KB Output is correct
15 Correct 1464 ms 1932 KB Output is correct
16 Correct 3742 ms 2880 KB Output is correct
17 Correct 4647 ms 3496 KB Output is correct
18 Correct 4863 ms 3496 KB Output is correct
19 Correct 4833 ms 3492 KB Output is correct
20 Correct 4577 ms 3500 KB Output is correct
21 Correct 4826 ms 3548 KB Output is correct
22 Correct 4400 ms 3532 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 372 KB Output is correct
3 Correct 0 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 734 ms 1364 KB Output is correct
8 Correct 899 ms 1484 KB Output is correct
9 Correct 1530 ms 2640 KB Output is correct
10 Correct 2624 ms 2660 KB Output is correct
11 Correct 2630 ms 2648 KB Output is correct
12 Correct 2812 ms 2640 KB Output is correct
13 Correct 2649 ms 2648 KB Output is correct
14 Correct 1760 ms 2032 KB Output is correct
15 Correct 1464 ms 1932 KB Output is correct
16 Correct 3742 ms 2880 KB Output is correct
17 Correct 4647 ms 3496 KB Output is correct
18 Correct 4863 ms 3496 KB Output is correct
19 Correct 4833 ms 3492 KB Output is correct
20 Correct 4577 ms 3500 KB Output is correct
21 Correct 4826 ms 3548 KB Output is correct
22 Correct 4400 ms 3532 KB Output is correct
23 Correct 8166 ms 7356 KB Output is correct
24 Correct 8685 ms 7500 KB Output is correct
25 Correct 7370 ms 7344 KB Output is correct
26 Execution timed out 9003 ms 7372 KB Time limit exceeded
27 Halted 0 ms 0 KB -