// 8.45
#ifndef HOME
#include "grader.h"
#endif
#include <bits/stdc++.h>
using namespace std;
const int DIM = 160005;
const int SQRT = 1005;
const int INF = 1000000005;
int n, l;
pair<int, int> ele[DIM], iele[DIM];
vector<pair<int, int>> buc[DIM / SQRT];
int cnt[DIM / SQRT][SQRT * 2];
int nxt[DIM / SQRT][SQRT * 2], whb[DIM];
void updateDp(int b) {
int s = (int) buc[b].size();
for (int i = s - 1; i >= 1; --i) {
if (buc[b][i - 1] > buc[b][i]) {
swap(buc[b][i - 1], buc[b][i]); }
else {
break; } }
for (int i = 0; i < s; ++i) {
whb[buc[b][i].second] = b; }
for (int i = s - 1, j = s; i >= 0; --i) {
while (buc[b][j - 1].first > buc[b][i].first + l) {
--j; }
if (j == s) {
cnt[b][i] = 1;
nxt[b][i] = buc[b][i].first + l; }
else {
cnt[b][i] = 1 + cnt[b][j];
nxt[b][i] = nxt[b][j]; } } }
void resetDp(void) {
for (int i = 0; i < n; ++i) {
ele[i] = iele[i]; }
sort(ele, ele + n);
for (int i = 0; i < n; ++i) {
if (i % SQRT == 0) {
buc[i / SQRT].clear(); }
buc[i / SQRT].push_back(ele[i]); }
for (int i = 0; i * SQRT < n; ++i) {
updateDp(i); } }
void init(int _n, int _l, int *X) {
n = _n; l = _l;
for (int i = 0; i < n; ++i) {
iele[i] = make_pair(X[i], i); }
iele[n] = make_pair(-INF, n); ++n;
while (n % SQRT != 0) {
iele[n] = make_pair(-INF, n); ++n; }
resetDp(); }
int query(void) {
int ans = 0;
for (int i = 0, v = -INF; i * SQRT < n; ++i) {
if (prev(buc[i].end()) -> first < v) {
continue; }
auto it = lower_bound(buc[i].begin(), buc[i].end(), make_pair(v, 0)) - buc[i].begin();
ans += cnt[i][it]; v = nxt[i][it] + 1; }
return ans; }
int update(int x, int c) {
static int nr = 0;
if (++nr == SQRT - 2) {
iele[x].first = c; resetDp(); nr = 0; }
else {
int wb = whb[x], ps = iele[x].first; iele[x].first = c;
buc[wb].erase(lower_bound(buc[wb].begin(), buc[wb].end(), make_pair(ps, x))); updateDp(wb);
if (prev(buc[n / SQRT - 1].end()) -> first <= c) {
buc[n / SQRT - 1].push_back(make_pair(c, x)); updateDp(n / SQRT - 1); }
else {
for (int i = 0; i * SQRT < n; ++i) {
if (buc[i].begin() -> first <= c and (prev(buc[i].end()) -> first >= c or buc[i + 1].begin() -> first >= c)) {
buc[i].push_back(make_pair(c, x)); updateDp(i); break; } } } }
return query() - 1; }
#ifdef HOME
int main(void) {
freopen("elephants.in", "r", stdin);
freopen("elephants.out", "w", stdout);
int N, L, M; cin >> N >> L >> M;
int *X = new int[N];
for (int i = 0; i < N; ++i) {
cin >> X[i]; }
init(N, L, X); int h = 0;
while (M--) {
int x, y, v; cin >> x >> y >> v; ++h;
int u = update(x, y);
if (update(x, y) != v) {
cout << h << " " << u << " " << v; return 0; } }
cout << "True";
return 0; }
#endif
Compilation message
elephants.cpp:3:11: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
