oj.uz

Submission #542478

# Submission time Handle Problem Language Result Execution time Memory
542478 2022-03-26T18:53:13 Z tabr Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 6648 KB 
#ifndef tabr
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif
#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];
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_ * (n <= 1000 ? 1 : 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;
}

#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 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 1 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 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 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 1 ms 340 KB Output is correct
7 Correct 833 ms 1548 KB Output is correct
8 Correct 1026 ms 1712 KB Output is correct
9 Correct 1720 ms 2792 KB Output is correct
10 Correct 2441 ms 2752 KB Output is correct
11 Correct 2395 ms 2736 KB Output is correct
12 Correct 2642 ms 2740 KB Output is correct
13 Correct 2532 ms 2736 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 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 1 ms 340 KB Output is correct
7 Correct 833 ms 1548 KB Output is correct
8 Correct 1026 ms 1712 KB Output is correct
9 Correct 1720 ms 2792 KB Output is correct
10 Correct 2441 ms 2752 KB Output is correct
11 Correct 2395 ms 2736 KB Output is correct
12 Correct 2642 ms 2740 KB Output is correct
13 Correct 2532 ms 2736 KB Output is correct
14 Correct 1670 ms 1944 KB Output is correct
15 Correct 1766 ms 2144 KB Output is correct
16 Correct 3432 ms 2968 KB Output is correct
17 Correct 4477 ms 3552 KB Output is correct
18 Correct 4738 ms 3556 KB Output is correct
19 Correct 5682 ms 3556 KB Output is correct
20 Correct 4448 ms 3552 KB Output is correct
21 Correct 4725 ms 3556 KB Output is correct
22 Correct 4513 ms 3556 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 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 1 ms 340 KB Output is correct
7 Correct 833 ms 1548 KB Output is correct
8 Correct 1026 ms 1712 KB Output is correct
9 Correct 1720 ms 2792 KB Output is correct
10 Correct 2441 ms 2752 KB Output is correct
11 Correct 2395 ms 2736 KB Output is correct
12 Correct 2642 ms 2740 KB Output is correct
13 Correct 2532 ms 2736 KB Output is correct
14 Correct 1670 ms 1944 KB Output is correct
15 Correct 1766 ms 2144 KB Output is correct
16 Correct 3432 ms 2968 KB Output is correct
17 Correct 4477 ms 3552 KB Output is correct
18 Correct 4738 ms 3556 KB Output is correct
19 Correct 5682 ms 3556 KB Output is correct
20 Correct 4448 ms 3552 KB Output is correct
21 Correct 4725 ms 3556 KB Output is correct
22 Correct 4513 ms 3556 KB Output is correct
23 Execution timed out 9048 ms 6648 KB Time limit exceeded
24 Halted 0 ms 0 KB -