oj.uz

Submission #542451

# Submission time Handle Problem Language Result Execution time Memory
542451 2022-03-26T18:13:51 Z tabr Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 7220 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_ * 1.3);
    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 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 332 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 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 668 ms 1492 KB Output is correct
8 Correct 773 ms 1880 KB Output is correct
9 Correct 1327 ms 2948 KB Output is correct
10 Correct 2108 ms 2952 KB Output is correct
11 Correct 2173 ms 2948 KB Output is correct
12 Correct 2399 ms 2956 KB Output is correct
13 Correct 2148 ms 2948 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 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 668 ms 1492 KB Output is correct
8 Correct 773 ms 1880 KB Output is correct
9 Correct 1327 ms 2948 KB Output is correct
10 Correct 2108 ms 2952 KB Output is correct
11 Correct 2173 ms 2948 KB Output is correct
12 Correct 2399 ms 2956 KB Output is correct
13 Correct 2148 ms 2948 KB Output is correct
14 Correct 1489 ms 2324 KB Output is correct
15 Correct 1236 ms 2376 KB Output is correct
16 Correct 3112 ms 2928 KB Output is correct
17 Correct 3774 ms 3596 KB Output is correct
18 Correct 4064 ms 3540 KB Output is correct
19 Correct 4066 ms 3524 KB Output is correct
20 Correct 3771 ms 3788 KB Output is correct
21 Correct 3957 ms 3540 KB Output is correct
22 Correct 3520 ms 3520 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 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 668 ms 1492 KB Output is correct
8 Correct 773 ms 1880 KB Output is correct
9 Correct 1327 ms 2948 KB Output is correct
10 Correct 2108 ms 2952 KB Output is correct
11 Correct 2173 ms 2948 KB Output is correct
12 Correct 2399 ms 2956 KB Output is correct
13 Correct 2148 ms 2948 KB Output is correct
14 Correct 1489 ms 2324 KB Output is correct
15 Correct 1236 ms 2376 KB Output is correct
16 Correct 3112 ms 2928 KB Output is correct
17 Correct 3774 ms 3596 KB Output is correct
18 Correct 4064 ms 3540 KB Output is correct
19 Correct 4066 ms 3524 KB Output is correct
20 Correct 3771 ms 3788 KB Output is correct
21 Correct 3957 ms 3540 KB Output is correct
22 Correct 3520 ms 3520 KB Output is correct
23 Correct 7778 ms 7216 KB Output is correct
24 Correct 8546 ms 7216 KB Output is correct
25 Correct 7389 ms 7220 KB Output is correct
26 Execution timed out 9060 ms 7204 KB Time limit exceeded
27 Halted 0 ms 0 KB -