Submission #56440

#	Time	Username	Problem	Language	Result	Execution time	Memory
56440		aquablitz11	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	8405 ms	125152 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;

const int N = 150010;
const int SN = 390;

int n, sn, l, X[N];
vector<int> elep[SN], cnt[N], rbnd[N];

int find_bucket(int x)
{
    for (int i = 0; i < sn; ++i) {
        if (!elep[i].empty() && x <= elep[i].back())
            return i;
    }
    return sn-1;
}

void process_bucket(int p)
{
    //fprintf(stderr, "process_bucket(%d):\n", p);
    int n = elep[p].size();
    cnt[p].resize(n);
    rbnd[p].resize(n);
    for (int i = n-1, j = n-1; i >= 0; --i) {
        while (elep[p][j]-elep[p][i] > l)
            --j;
        cnt[p][i] = j == n-1 ? 1 : (1 + cnt[p][j+1]);
        rbnd[p][i] = j == n-1 ? (elep[p][i]+l) : rbnd[p][j+1];
    }
    /*for (int i = 0; i < n; ++i) {
        if (i != 0) fprintf(stderr, " ");
        fprintf(stderr, "%3d", elep[p][i]);
    }
    fprintf(stderr, "\n");
    for (int i = 0; i < n; ++i) {
        if (i != 0) fprintf(stderr, " ");
        fprintf(stderr, "%3d", cnt[p][i]);
    }
    fprintf(stderr, "\n");
    for (int i = 0; i < n; ++i) {
        if (i != 0) fprintf(stderr, " ");
        fprintf(stderr, "%3d", rbnd[p][i]);
    }
    fprintf(stderr, "\n");
    fprintf(stderr, "\n");*/
}

void process_all()
{
    //fprintf(stderr, "process_all():\n");
    vector<int> X(::X, ::X+n);
    sort(X.begin(), X.end());
    for (int i = 0; i < sn; ++i) {
        elep[i].clear();
        elep[i].reserve(3*sn);
    }
    for (int i = 0; i < n; ++i) {
        int b = i/sn;
        if (b >= sn) b = sn-1;
        elep[b].push_back(X[i]);
        //fprintf(stderr, "add elephant X = %d to block %d\n", X[i], b);
    }
    //fprintf(stderr, "\n");
    for (int i = 0; i < sn; ++i)
        process_bucket(i);
}

void init(int n, int l, int X[])
{
    ::n = n, ::l = l, ::sn = sqrt(n);
    for (int i = 0; i < n; ++i)
        ::X[i] = X[i];
    process_all();
}

int cnt_upd = 0;
bool force = false;
bool skip = false;
int update(int i, int y)
{
    //fprintf(stderr, "update(%d, %d):\n", i, y);
    if (force || (!skip && ((++cnt_upd) % sn == 0))) {
        X[i] = y;
        process_all();
    } else {
        int bx = find_bucket(X[i]);
        int by = find_bucket(y);
        elep[bx].erase(find(elep[bx].begin(), elep[bx].end(), X[i]));
        elep[by].insert(lower_bound(elep[by].begin(), elep[by].end(), y), y);
        //fprintf(stderr, "%d is in bucket %d, %d is in bucket %d\n", X[i], bx, y, by);
        process_bucket(bx);
        if (bx != by) process_bucket(by);
        X[i] = y;
    }
    //fprintf(stderr, "\n");

    int ans = 0, last = -1;
    for (int b = 0; b < sn; ++b) {
        int i = upper_bound(elep[b].begin(), elep[b].end(), last) - elep[b].begin();
        if (i < elep[b].size()) {
            //fprintf(stderr, "block %d, got elephant %d: %d %d %d\n", b, i, elep[b][i], cnt[b][i], rbnd[b][i]);
            ans += cnt[b][i];
            last = rbnd[b][i];
        }
    }

    return ans;
}

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:102:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < elep[b].size()) {
             ~~^~~~~~~~~~~~~~~~

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