oj.uz

Submission #542505

# Submission time Handle Problem Language Result Execution time Memory
542505 2022-03-26T19:37:51 Z tabr Dancing Elephants (IOI11_elephants) C++17
50 / 100
 3614 ms 3344 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 = 500;
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 * 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;
}

mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

int rand_int(int a, int b) {  // [a, b]
    return uniform_int_distribution<int>(a, b)(rng);
}

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 1 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 1 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 537 ms 1420 KB Output is correct
8 Correct 659 ms 1568 KB Output is correct
9 Correct 1035 ms 2496 KB Output is correct
10 Correct 1568 ms 2504 KB Output is correct
11 Correct 1548 ms 2516 KB Output is correct
12 Correct 1835 ms 2504 KB Output is correct
13 Correct 1573 ms 2516 KB Output is correct

Subtask #4
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 1 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 537 ms 1420 KB Output is correct
8 Correct 659 ms 1568 KB Output is correct
9 Correct 1035 ms 2496 KB Output is correct
10 Correct 1568 ms 2504 KB Output is correct
11 Correct 1548 ms 2516 KB Output is correct
12 Correct 1835 ms 2504 KB Output is correct
13 Correct 1573 ms 2516 KB Output is correct
14 Correct 903 ms 1808 KB Output is correct
15 Correct 1160 ms 1992 KB Output is correct
16 Correct 2501 ms 2740 KB Output is correct
17 Correct 3072 ms 3292 KB Output is correct
18 Correct 3614 ms 3272 KB Output is correct
19 Incorrect 40 ms 3344 KB Output isn't correct
20 Halted 0 ms 0 KB -

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 1 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 537 ms 1420 KB Output is correct
8 Correct 659 ms 1568 KB Output is correct
9 Correct 1035 ms 2496 KB Output is correct
10 Correct 1568 ms 2504 KB Output is correct
11 Correct 1548 ms 2516 KB Output is correct
12 Correct 1835 ms 2504 KB Output is correct
13 Correct 1573 ms 2516 KB Output is correct
14 Correct 903 ms 1808 KB Output is correct
15 Correct 1160 ms 1992 KB Output is correct
16 Correct 2501 ms 2740 KB Output is correct
17 Correct 3072 ms 3292 KB Output is correct
18 Correct 3614 ms 3272 KB Output is correct
19 Incorrect 40 ms 3344 KB Output isn't correct
20 Halted 0 ms 0 KB -