oj.uz

Submission #542492

# Submission time Handle Problem Language Result Execution time Memory
542492 2022-03-26T19:05:42 Z tabr Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 6860 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 * 1.2);
    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 1 ms 384 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 1 ms 384 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 1 ms 384 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 924 ms 1616 KB Output is correct
8 Correct 1098 ms 1800 KB Output is correct
9 Correct 2086 ms 2880 KB Output is correct
10 Correct 3011 ms 2880 KB Output is correct
11 Correct 2882 ms 2880 KB Output is correct
12 Correct 3000 ms 2880 KB Output is correct
13 Correct 2991 ms 2900 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 1 ms 384 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 924 ms 1616 KB Output is correct
8 Correct 1098 ms 1800 KB Output is correct
9 Correct 2086 ms 2880 KB Output is correct
10 Correct 3011 ms 2880 KB Output is correct
11 Correct 2882 ms 2880 KB Output is correct
12 Correct 3000 ms 2880 KB Output is correct
13 Correct 2991 ms 2900 KB Output is correct
14 Correct 1713 ms 2028 KB Output is correct
15 Correct 1852 ms 2260 KB Output is correct
16 Correct 3874 ms 3112 KB Output is correct
17 Correct 4663 ms 3720 KB Output is correct
18 Correct 5084 ms 3720 KB Output is correct
19 Correct 5966 ms 3716 KB Output is correct
20 Correct 4650 ms 3796 KB Output is correct
21 Correct 4993 ms 3724 KB Output is correct
22 Correct 5058 ms 3716 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 1 ms 384 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 924 ms 1616 KB Output is correct
8 Correct 1098 ms 1800 KB Output is correct
9 Correct 2086 ms 2880 KB Output is correct
10 Correct 3011 ms 2880 KB Output is correct
11 Correct 2882 ms 2880 KB Output is correct
12 Correct 3000 ms 2880 KB Output is correct
13 Correct 2991 ms 2900 KB Output is correct
14 Correct 1713 ms 2028 KB Output is correct
15 Correct 1852 ms 2260 KB Output is correct
16 Correct 3874 ms 3112 KB Output is correct
17 Correct 4663 ms 3720 KB Output is correct
18 Correct 5084 ms 3720 KB Output is correct
19 Correct 5966 ms 3716 KB Output is correct
20 Correct 4650 ms 3796 KB Output is correct
21 Correct 4993 ms 3724 KB Output is correct
22 Correct 5058 ms 3716 KB Output is correct
23 Execution timed out 9073 ms 6860 KB Time limit exceeded
24 Halted 0 ms 0 KB -