Submission #291110

#	Time	Username	Problem	Language	Result	Execution time	Memory
291110		Kastanda	Dancing Elephants (IOI11_elephants)	C++11	100 / 100	6461 ms	12840 KiB

elephants

// M
#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;
typedef long long ll;
const int N = 151234, SQ = 700, QS = N / SQ + 4, SCALE = N * 3;
int n, nsq, lzcnt, EXTRAS, B[N];
ll k, X[N];
vector < ll > V[QS];
vector < pair < int , ll > > dp[QS];
inline void Build(int block)
{
        int sz = (int)V[block].size();
        assert(sz >= 1); // For convenience.

        dp[block].resize(sz);
        int r = sz;
        for (int i = sz - 1; i >= 0; i --)
        {
                while (V[block][r - 1] > V[block][i] + k)
                        r --;
                if (r < sz)
                        dp[block][i] = {dp[block][r].first + 1, dp[block][r].second};
                else
                        dp[block][i] = {1, V[block][i] + k};
        }
}
inline void Erase(int block, ll val)
{
        for (int i = 0; i < (int)V[block].size(); i ++)
                if (V[block][i] == val)
                {
                        V[block].erase(V[block].begin() + i);
                        break;
                }
        Build(block);
}
inline void Insert(int block, ll val)
{
        int i = 0;
        while (i < (int)V[block].size() && V[block][i] < val)
                i ++;
        V[block].insert(V[block].begin() + i, val);
        Build(block);
}
inline void Refresh()
{
        lzcnt = 0;
        vector < int > srt(n, 0);
        for (int i = 0; i < n; i ++)
                srt[i] = i;
        sort(srt.begin(), srt.end(), [&](int i, int j){return X[i] < X[j];});
        for (int i = 0; i < nsq; i ++)
                V[i].clear();
        for (int i = 0; i < n; i ++)
                V[i / SQ].push_back(X[srt[i]]), B[srt[i]] = i / SQ;
        for (int i = 0; i < nsq; i ++)
                Build(i);
}
inline int Calculate()
{
        int Cnt = 0;
        ll nw = -1e18;
        for (int block = 0; block < nsq; block ++)
                if (V[block].size() && V[block].back() > nw)
                {
                        int lb = upper_bound(V[block].begin(), V[block].end(), nw) - V[block].begin();
                        assert(lb < (int)V[block].size());
                        Cnt += dp[block][lb].first;
                        nw = dp[block][lb].second;
                }
        return Cnt - EXTRAS;
}

void init(int _n, int _k, int _X[])
{
        n = _n;
        k = (ll)_k * SCALE + n;
        for (int i = 0; i < n; i ++)
                X[i] = _X[i] * (ll)SCALE + i;
        ll val = (ll)(2e9 + 9);
        while (n % SQ != 0)
                X[n] = val * SCALE + n, n ++, val += (ll)(1e9 + 9), EXTRAS ++;
        for (int i = 0; i < n; i ++)
                V[i / SQ].push_back(X[i]), B[i] = i / SQ;
        assert(n % SQ == 0);
        nsq = n / SQ;
        for (int i = 0; i < nsq; i ++)
                Build(i);
}

int update(int i, int y)
{
        lzcnt ++;
        if (lzcnt + 3 >= SQ)
                Refresh();

        // If some stuff, refresh the data structure ...

        ll val = y * (ll)SCALE + i;

        // Removing the i-th element from it's block
        {
                int block = B[i];
                Erase(block, X[i]);
        }

        // Adding the i-th element to it's new block
        {
                int block = 0;
                for (; block < nsq; block ++)
                        if (block + 1 == nsq || V[block + 1][0] > val)
                                break;
                if (block == nsq)
                        block --;
                X[i] = val;
                B[i] = block;
                Insert(block, X[i]);
        }

        // Calculating the result :
        return Calculate();
}

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