Submission #1188209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188209		Lithanium	Dancing Elephants (IOI11_elephants)	C++20	97 / 100	9091 ms	20296 KiB

elephants

#pragma GCC optimize("Ofast,unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
constexpr int K = 300;
 
int loc[150005];
int old[150005];
set<pair<int, int>> batch, all, extra;
bitset<150005> seen;
int lift[14][150005];
int N, L;
 
inline void calc() {
    vector<pair<int, int>> order(N);
    for (int i = 0; i < N; i ++) order[i] = {loc[i], i};
    sort(order.begin(), order.end());
    for (int i = 0; i < N; i ++) {
        old[i] = loc[i];
        int t = lower_bound(order.begin(), order.end(), make_pair(order[i].first + L + 1, -1)) - order.begin();
        lift[0][order[i].second] = N;
        if (t < N) lift[0][order[i].second] = order[t].second;
    }
    lift[0][N] = N;
    for (int i = 1; i < 14; i ++) {
        for (int j = 0; j <= N; j ++) {
            lift[i][j] = lift[i-1][lift[i-1][j]];
        }
    }
    seen.reset();
    batch = {make_pair(2e9+5, N)};
    extra = {make_pair(2e9+5, N)};
}
 
void init(int n, int l, int X[]) {
    N = n, L = l;
    for (int i = 0; i < N; i ++) {
        loc[i] = X[i];
        old[i] = X[i];
        lift[0][i] = lower_bound(X, X+N, loc[i] + L + 1) - X;
        all.insert({X[i], i});
    }
    old[N] = 2e9+5;
    loc[N] = 2e9+5;
    all.insert({2e9+5, N});
    lift[0][N] = N;
    for (int i = 1; i < 14; i ++) {
        for (int j = 0; j <= N; j ++) {
            lift[i][j] = lift[i-1][lift[i-1][j]];
        }
    }
    extra.insert({2e9+5, N});
    batch.insert({2e9+5, N});
}
 
int update(int i, int y) {
    all.erase({loc[i], i});
    all.insert({y, i});
    if (seen[i]) {
        batch.erase({loc[i], i});
        batch.insert({y, i});
    } else {
        seen[i] = 1;
        extra.insert({old[i], i});
        batch.insert({y, i});
    }
    loc[i] = y;
    if (batch.size() == K) calc();
    auto it = batch.begin(), it2 = extra.begin();
    int upto = all.begin()->second, ans = 0;
    while (upto < N) {
        // see how far it can be placed
        if (upto != it->second) {
            // there are some disruptor events
            for (int i = 13; i >= 0; i --) if (old[lift[i][upto]] < min(it2->first, it->first)) {
                upto = lift[i][upto];
                ans += (1 << i);
            }
        }
        if (upto == N) return ans;
        // forced placements
        do {
            ans ++;
            upto = all.lower_bound(make_pair(loc[upto] + L + 1, -1))->second;
            while (it->first < loc[upto]) it = next(it);
            while (it2->first < loc[upto]) it2 = next(it2);
        } while (upto < N and it->first <= loc[upto] + L + 1);
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3