#include "grader.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
*/
Compilation message
elephants.cpp:1:10: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
