제출 #1224857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224857		ericl23302	코끼리 (Dancing Elephants) (IOI11_elephants)	C++20	26 / 100	8 ms	1348 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) {
    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();
    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 << '\n';
    cout << "Positions: \n";
    for (int &i : positions) cout << i << ' ';
    cout << '\n';
    cout << "Buckets: \n";
    for (auto &i : buckets) {
        for (int &j : i) cout << j << ' ';
        cout << '\n';
    }
    cout << "Bucket Starts: \n";
    for (int &i : bucketStarts) cout << i << ' ';
    cout << '\n';
    cout << "Bucket Ends: \n";
    for (int &i : bucketEnds) cout << i << ' ';
    cout << '\n';

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

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

    int j = 0;
    while (j < bucketCount) {
        ++j;
        if (curEnd >= bucketEnds[j]) continue;
        int pos = upper_bound(buckets[j].begin(), buckets[j].end(), curEnd) - buckets[j].begin();
        curRes += bucketDps[j][pos].first;
        curEnd = bucketDps[j][pos].second;
    }

    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);

    return solve();
}

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