oj.uz

Submission #542294

# Submission time Handle Problem Language Result Execution time Memory
542294 2022-03-26T05:21:24 Z tabr Dancing Elephants (IOI11_elephants) C++17
0 / 100
 1 ms 596 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_);
    for (int i = 0; i < n; i++) {
        x[i] = x_[i];
    }
}

void build_one(int id) {
    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[i] = 1;
            jump_pos[i] = x[e[id][i]] + l + 1;
        } else {
            jump_cnt[i] = jump_cnt[j] + 1;
            jump_pos[i] = jump_pos[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 (upd_cnt == 0) {
        build();
    }
    upd_cnt++;
    if (upd_cnt == n / B) {
        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 (!e[id].empty() && e[id][0] <= y && y <= e[id].back()) {
            e[id].emplace_back(i);
            build_one(id);
        }
        assert(id < B - 1);
    }
    // answer
    int ans = 0;
    int now = 0;
    for (int id = 0; id < B; id++) {
        if (e[id].empty()) {
            continue;
        }
        auto iter = lower_bound(e[id].begin(), e[id].end(), now, [&](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);
    return 0;
}
#endif

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -