Submission #1224871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224871		ericl23302	Dancing Elephants (IOI11_elephants)	C++20	100 / 100	5362 ms	5956 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

const int k = 400;

int n, l, cnt = 0;
vector<int> positions;
vector<vector<int>> buckets;
vector<int> bucketStarts, bucketEnds;
vector<vector<pair<int, int>>> bucketDps;

void doDp(int bucket) {
    // cout << "Do DP: " << bucket << endl;
    vector<int> &curBucket = buckets[bucket];
    vector<pair<int, int>> &curDp = bucketDps[bucket];
    int sz = curBucket.size();
    if (!sz) {
        bucketStarts[bucket] = (bucket ? bucketStarts[bucket - 1] : -1);
        bucketEnds[bucket] = (bucket ? bucketEnds[bucket - 1] : -1);
        return;
    }

    curDp.assign(sz, {0, 0});
    curDp[sz - 1] = {1, curBucket[sz - 1] + l};
    int j = sz - 1;
    for (int i = sz - 2; i >= 0; --i) {
        while (curBucket[j] > curBucket[i] + l) --j;
        if (j < sz - 1) curDp[i] = {1 + curDp[j + 1].first, curDp[j + 1].second};
        else curDp[i] = {1, curBucket[i] + l};
    }

    bucketStarts[bucket] = curBucket[0];
    bucketEnds[bucket] = curBucket[sz - 1];
}

void build() {
    buckets.clear();
    bucketStarts.clear();
    bucketEnds.clear();
    bucketDps.clear();
    vector<int> elephants(n);
    for (int i = 0; i < n; ++i) elephants[i] = positions[i];
    sort(elephants.begin(), elephants.end());
    buckets.resize((n - 1) / k + 1);
    for (int i = 0; i < n; ++i) buckets[i / k].push_back(elephants[i]);
    for (int i = 0; i < buckets.size(); ++i) bucketDps.push_back({}), bucketStarts.push_back(-1), bucketEnds.push_back(-1), doDp(i);
}

void print()
{
    cout << n << ' ' << l << ' ' << cnt << endl;
    cout << "Positions: " << endl;
    for (int &i : positions) cout << i << ' ';
    cout << endl;
    cout << "Buckets: " << endl;
    for (auto &i : buckets) {
        for (int &j : i) cout << j << ' ';
        cout << endl;
    }
    cout << "Bucket Starts: " << endl;
    for (int &i : bucketStarts) cout << i << ' ';
    cout << endl;
    cout << "Bucket Ends: " << endl;
    for (int &i : bucketEnds) cout << i << ' ';
    cout << endl;

    cout << "Bucket DP: " << endl;
    for (auto &i : bucketDps) {
        for (auto &j : i) cout << j.first << ' ' << j.second << "   ";
        cout << endl;
    }
}

int solve() {
    // print();
    int curRes = 0, curEnd = 0;
    int bucketCount = buckets.size();
    for (int i = 0; i < bucketCount; ++i) {
        if (!buckets[i].empty()) {
            curRes = bucketDps[i][0].first, curEnd = bucketDps[i][0].second;
            break;
        }
    }

    // cout << "SOLVE: " << endl;
    // cout << curRes << ' ' << curEnd << endl;

    int j = 0;
    while (j < bucketCount - 1) {
        ++j;
        // cout << "J(0): " << j << endl;
        if (curEnd >= bucketEnds[j]) continue;
        // cout << "J(1): " << j << endl;
        int pos = upper_bound(buckets[j].begin(), buckets[j].end(), curEnd) - buckets[j].begin();
        // cout << "POS: " << pos << endl;
        curRes += bucketDps[j][pos].first;
        curEnd = bucketDps[j][pos].second;
        // cout << curRes << ' ' << curEnd << endl;
    }

    return curRes;
}

void init(int N, int L, int X[])
{
    n = N;
    l = L;
    for (int i = 0; i < N; ++i) positions.push_back(X[i]);
}

int update(int i, int y)
{
    if (cnt % k == 0) build();
    int bucketCount = buckets.size();
    int a = 0, b = 0;
    while (a < bucketCount) {
        if (bucketEnds[a] >= positions[i]) break;
        ++a;
    }

    while (b < bucketCount) {
        if (bucketEnds[b] >= y) break;
        ++b;
    }
    b = min(b, bucketCount - 1);

    buckets[a].erase(lower_bound(buckets[a].begin(), buckets[a].end(), positions[i]));
    positions[i] = y;
    buckets[b].push_back(positions[i]);
    sort(buckets[b].begin(), buckets[b].end());
    doDp(a);
    if (a != b) doDp(b);

    ++cnt;

    return solve();
}

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