Submission #221451

#	Time	Username	Problem	Language	Result	Execution time	Memory
221451		emil_physmath	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	7935 ms	12220 KiB

elephants

#include "elephants.h"
#include <algorithm>
#include <vector>
using namespace std;
const int mag = 380;
struct Block
{
    Block()
        : a()
        , cnt()
        , upto()
    {}

    vector<int> a;
    vector<int> cnt;
    vector<int> upto;
};

int n;
int len;
int x[150000];
int blof[150000];
vector<Block> blocks;

void SetBlock(Block& block)
{
    if (block.a.empty())
    {
        block.upto.clear();
        block.cnt.clear();
        return;
    }
    vector<int>& a = block.a;
    vector<int>& cnt = block.cnt;
    cnt.resize(a.size());
    vector<int>& upto = block.upto;
    upto.resize(a.size());
    cnt.back() = 1;
    int uptoind = (int)a.size() - 1;
    upto.back() = a.back() + len;
    for (int j = (int)a.size() - 2; j >= 0; --j)
    {
        while (a[uptoind] - a[j] > len) --uptoind;
        cnt[j] = 1 + (uptoind + 1 == (int)a.size() ? 0 : cnt[uptoind + 1]);
        upto[j] = (uptoind + 1 == (int)a.size() ? a[j] + len : upto[uptoind + 1]);
    }
}
void Init()
{
    blocks.clear();
    vector<pair<int, int> > y(n);
    for (int i = 0; i < n; ++i)
        y[i] = {x[i], i};
    sort(y.begin(), y.end());
    for (int i = 0; i < n; ++i)
        blof[y[i].second] = i / mag;
    for (int i = 0; i < n; i += mag)
    {
        blocks.push_back(Block());
        blocks.back().a.clear();
        for (int j = i; j < min(i + mag, n); ++j)
            blocks.back().a.push_back(y[j].first);
        SetBlock(blocks.back());
    }
}
int update(int id, int nv)
{
    static int upds = 0;
    vector<int>* a = &blocks[blof[id]].a;
    a->erase(find(a->begin(), a->end(), x[id]));
    SetBlock(blocks[blof[id]]);
    vector<int> temp;
    for (int i = 0; i < (int)blocks.size(); ++i)
        if (!blocks[i].a.empty())
            temp.push_back(i);
    auto it = upper_bound(temp.begin(), temp.end(), nv, [](int y, int bl) {
        return y < blocks[bl].a.back();
    });
    blof[id] = (it == temp.end() ? (int)blocks.size() - 1 : *it);
    a = &blocks[blof[id]].a;
    a->insert(upper_bound(a->begin(), a->end(), nv), nv);
    SetBlock(blocks[blof[id]]);
    x[id] = nv;
    if (++upds >= mag)
    {
        upds = 0;
        Init();
    }
    int res = 0;
    int upto = -1;
    for (int bl = 0; bl < (int)blocks.size(); ++bl)
    {
        int i = upper_bound(blocks[bl].a.begin(), blocks[bl].a.end(), upto) - blocks[bl].a.begin();
        if (i < (int)blocks[bl].a.size())
        {
            res += blocks[bl].cnt[i];
            upto = blocks[bl].upto[i];
        }
    }
    return res;
}
void init(int n_, int len_, int x_[])
{
    n = n_;
    len = len_;
    for (int i = 0; i < n; ++i)
        x[i] = x_[i];
    Init();
}
/*
5 10 5
1
1
1
1
1

0 10
1 20
2 11
3 31
4 33
*/

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