#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
const int kN = 1e5 + 5e4;
const int bucketSize = 2;
const int kBuckets = 1e5;
int n, len, a[kN], bucket[kN], indexInBucket[kN];
int updates;
int auxSize, auxIndices[kN];
class bucket_t {
private:
int N, indices[2 * bucketSize];
int req[2 * bucketSize], maxReach[2 * bucketSize];
public:
void reset() {
N = 0;
}
bool isEmpty() {
return N == 0;
}
int getSize() {
return N;
}
int first() {
return a[indices[0]];
}
int last() {
return a[indices[N - 1]];
}
void add(int index) {
indices[N] = index;
N += 1;
}
void addAll() {
for (int i = 0; i < N; ++i) {
auxIndices[auxSize] = indices[i];
auxSize += 1;
}
}
int jumps(int index) {
return req[index];
}
int furthest(int index) {
return maxReach[index];
}
void build() {
int r = N - 1;
for (int l = N - 1; l >= 0; --l) {
while (a[indices[r]] - a[indices[l]] > len) {
r -= 1;
}
if (r == N - 1) {
req[l] = 1;
maxReach[l] = a[indices[l]] + len;
} else {
req[l] = req[r + 1] + 1;
maxReach[l] = maxReach[r + 1];
}
}
}
void rem(int pos) {
for (int i = pos; i < N - 1; ++i) {
indices[i] = indices[i + 1];
indexInBucket[indices[i]] = i;
}
N -= 1;
build();
}
void ins(int index) {
int ptr = N - 1;
while (ptr >= 0 && a[index] < a[indices[ptr]]) {
ptr -= 1;
}
for (int i = N; i > ptr + 1; --i) {
indices[i] = indices[i - 1];
indexInBucket[indices[i]] = i;
}
indices[ptr + 1] = index;
indexInBucket[index] = ptr + 1;
N += 1;
build();
}
int upperBound(int x) {
int l = -1, r = N;
while (r - l > 1) {
int mid = (l + r) / 2;
if (mid != -1 && (mid == N || x < a[indices[mid]])) {
r = mid;
} else {
l = mid;
}
}
return r;
}
} buckets[kBuckets];
void init(int N, int L, int X[]) {
n = N;
len = L;
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
buckets[i].reset();
}
for (int i = 0; i < n; ++i) {
a[i] = X[i];
bucket[i] = i / bucketSize;
indexInBucket[i] = i % bucketSize;
buckets[i / bucketSize].add(i);
}
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
buckets[i].build();
}
}
void rebuild() {
auxSize = 0;
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
buckets[i].addAll();
}
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
buckets[i].reset();
}
for (int i = 0; i < n; ++i) {
bucket[auxIndices[i]] = i / bucketSize;
indexInBucket[auxIndices[i]] = i % bucketSize;
buckets[i / bucketSize].add(auxIndices[i]);
}
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
buckets[i].build();
}
}
int query() {
int res = 0;
int value = -1;
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
if (!buckets[i].isEmpty()) {
int index = buckets[i].upperBound(value);
if (index != buckets[i].getSize()) {
res += buckets[i].jumps(index);
value = buckets[i].furthest(index);
}
}
}
return res;
}
int update(int index, int x) {
buckets[bucket[index]].rem(indexInBucket[index]);
a[index] = x;
int firstBucket = 0, lastBucket = 0, newBucket = -1;
for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
if (!buckets[i].isEmpty()) {
if (firstBucket == -1) {
firstBucket = i;
}
lastBucket = i;
if (buckets[i].first() <= x && x <= buckets[i].last()) {
newBucket = i;
}
}
}
if (newBucket == -1) {
if (x < buckets[firstBucket].first()) {
newBucket = firstBucket;
} else {
newBucket = lastBucket;
}
}
bucket[index] = newBucket;
buckets[newBucket].ins(index);
updates += 1;
if (updates == bucketSize) {
rebuild();
updates = 0;
}
return query();
}
/*
4 10 5
10
15
17
20
2 16 1
1 25 2
3 35 2
0 38 2
2 0 3
#define MAX_N 1000000
#define MAX_M 1000000
static int N,L,M;
static int X[MAX_N];
static int ii[MAX_M];
static int yy[MAX_M];
static int sol[MAX_M];
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&L,&M));
for(i=0; i<N; i++)
my_assert(1==scanf("%d",&X[i]));
for(i=0; i<M; i++)
my_assert(3==scanf("%d %d %d",&ii[i],&yy[i],&sol[i]));
}
int main()
{
int i, ans;
read_input();
init(N,L,X);
for(i=0; i<M; i++) {
ans = update(ii[i],yy[i]);
if(ans==sol[i])continue;
printf("Incorrect. In %d-th move, answered %d (%d expected).\n",
i+1, ans, sol[i]);
return 0;
}
printf("Correct.\n");
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
