oj.uz

Submission #542500

# Submission time Handle Problem Language Result Execution time Memory
542500 2022-03-26T19:16:35 Z tabr Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 7060 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];

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];
    }
}

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() {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](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 0 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 0 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 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 1 ms 340 KB Output is correct
3 Correct 1 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 650 ms 1344 KB Output is correct
8 Correct 764 ms 1500 KB Output is correct
9 Correct 1298 ms 2552 KB Output is correct
10 Correct 1432 ms 2552 KB Output is correct
11 Correct 1507 ms 2560 KB Output is correct
12 Correct 2309 ms 2576 KB Output is correct
13 Correct 1465 ms 2556 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 650 ms 1344 KB Output is correct
8 Correct 764 ms 1500 KB Output is correct
9 Correct 1298 ms 2552 KB Output is correct
10 Correct 1432 ms 2552 KB Output is correct
11 Correct 1507 ms 2560 KB Output is correct
12 Correct 2309 ms 2576 KB Output is correct
13 Correct 1465 ms 2556 KB Output is correct
14 Correct 1438 ms 1800 KB Output is correct
15 Correct 1377 ms 1976 KB Output is correct
16 Correct 3679 ms 2784 KB Output is correct
17 Correct 4165 ms 3404 KB Output is correct
18 Correct 4278 ms 3408 KB Output is correct
19 Correct 3416 ms 3388 KB Output is correct
20 Correct 3998 ms 3508 KB Output is correct
21 Correct 4142 ms 3408 KB Output is correct
22 Correct 2798 ms 3412 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 650 ms 1344 KB Output is correct
8 Correct 764 ms 1500 KB Output is correct
9 Correct 1298 ms 2552 KB Output is correct
10 Correct 1432 ms 2552 KB Output is correct
11 Correct 1507 ms 2560 KB Output is correct
12 Correct 2309 ms 2576 KB Output is correct
13 Correct 1465 ms 2556 KB Output is correct
14 Correct 1438 ms 1800 KB Output is correct
15 Correct 1377 ms 1976 KB Output is correct
16 Correct 3679 ms 2784 KB Output is correct
17 Correct 4165 ms 3404 KB Output is correct
18 Correct 4278 ms 3408 KB Output is correct
19 Correct 3416 ms 3388 KB Output is correct
20 Correct 3998 ms 3508 KB Output is correct
21 Correct 4142 ms 3408 KB Output is correct
22 Correct 2798 ms 3412 KB Output is correct
23 Correct 8421 ms 7060 KB Output is correct
24 Execution timed out 9092 ms 6992 KB Time limit exceeded
25 Halted 0 ms 0 KB -