#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int blockSize = 800, resetCycle = 200, mn = 150'005;
int n, L, queryCount, save[mn];
struct block {
vector<int> x, jumpTo, step;
void refine (int pos) {
int iter = upper_bound(all(x), x[pos] + L) - x.begin();
for (int i = pos; i >= 0; i--) {
while (iter - 1 >= 0 && x[iter - 1] - x[i] > L) iter--;
if (iter == x.size()) jumpTo[i] = x[i] + L, step[i] = 1;
else jumpTo[i] = jumpTo[iter], step[i] = step[iter] + 1;
}
}
block (vector<int> x) : x(x), jumpTo(x.size()), step(x.size()) { refine((int)x.size() - 1); }
void insert (int xP) {
int pos = upper_bound(all(x), xP) - x.begin();
x.insert(x.begin() + pos, xP);
jumpTo.insert(jumpTo.begin() + pos, 0);
step.insert(step.begin() + pos, 0);
refine(pos);
}
void remove (int xP) {
int pos = lower_bound(all(x), xP) - x.begin();
x.erase(x.begin() + pos);
jumpTo.erase(jumpTo.begin() + pos);
step.erase(step.begin() + pos);
refine(pos);
}
void batchJump (int &start, int &ans) {
assert(x.size() < (1 << 10));
if (x[0] > start) return start = jumpTo[0], ans += step[0], void();
int pos = 0;
for (int mask = 1 << 9; mask; mask >>= 1) {
if ((pos | mask) >= x.size()) continue;
if (x[pos | mask] <= start) pos |= mask;
}
pos++;
if (pos < x.size()) start = jumpTo[pos], ans += step[pos];
}
int last() { return x.back(); }
};
vector<block> blocks;
void build (const vector<int> &x) {
for (int i = 0; i < x.size(); i += blockSize) {
vector<int> cur(x.begin() + i, x.begin() + min((int)x.size(), i + blockSize));
blocks.emplace_back(cur);
}
}
void reBuild() {
while (true);
vector<int> x;
for (block &cur : blocks)
for (int u : cur.x) x.push_back(u);
blocks.clear(), build(x);
}
void insert (int xP) {
for (block &cur : blocks)
if (cur.last() >= xP) return cur.insert(xP), void();
blocks[(int)blocks.size() - 1].insert(xP);
}
void remove (int xP) {
for (block &cur : blocks)
if (cur.last() >= xP) return cur.remove(xP), void();
}
int query() {
int curPos = -1, ans = 0;
for (block &cur : blocks) cur.batchJump(curPos, ans);
return ans;
}
void init (int _n, int _L, int X[]) {
n = _n, L = _L;
vector<int> vec(n);
for (int i = 0; i < n; i++) vec[i] = save[i] = X[i];
build(vec);
}
int update (int i, int y) {
if (queryCount && (queryCount++) % resetCycle == 0) reBuild();
remove(save[i]), insert(y), save[i] = y;
return query();
}
Compilation message
elephants.cpp: In member function 'void block::refine(int)':
elephants.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if (iter == x.size()) jumpTo[i] = x[i] + L, step[i] = 1;
| ~~~~~^~~~~~~~~~~
elephants.cpp: In member function 'void block::batchJump(int&, int&)':
elephants.cpp:52:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if ((pos | mask) >= x.size()) continue;
| ~~~~~~~~~~~~~^~~~~~~~~~~
elephants.cpp:56:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if (pos < x.size()) start = jumpTo[pos], ans += step[pos];
| ~~~~^~~~~~~~~~
elephants.cpp: In function 'void build(const std::vector<int>&)':
elephants.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < x.size(); i += blockSize) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2404 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2404 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2404 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Runtime error |
16 ms |
3152 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2404 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Runtime error |
16 ms |
3152 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2404 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Runtime error |
16 ms |
3152 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
