#include "elephants.h"
#include <iostream>
#include <set>
#include <utility>
#include <cassert>
#define MAXN 70005
#define K 250
#define LOG 16
using namespace std;
int N, L, Q, Pos[MAXN];
bool stray[MAXN];
multiset <pair <int,int> > E, G, S; //all elephants: pos = id and ghost: pos = id
int nxt[MAXN][20];
void makeJump() {
for (int i=0; i<=N; i++) {
auto it = E.upper_bound({Pos[i] + L,MAXN});
if (it == E.end()) {
nxt[i][0] = N;
} else {
nxt[i][0] = (*it).second;
}
//printf("%d %d\n",i,nxt[i][0]);
}
for (int i=1; i<LOG; i++) {
for (int j=0; j<=N; j++) {
nxt[j][i] = nxt[nxt[j][i-1]][i-1];
}
}
}
int Next(int p) {
auto it = E.upper_bound({p + L,MAXN});
if (it == E.end()) {
return(N);
} else {
return((*it).second);
}
}
void init(int n, int l, int x[])
{
N= n, L = l;
for (int i=0; i<n; i++) {
Pos[i] = x[i];
E.insert({x[i], i});
}
E.insert({(int) 2e9 + 5, N}); //dummy
Pos[N] = (int) 2e9 + 5;
makeJump();
}
int update(int i, int y)
{
Q+=1;
if (stray[i]) {
S.erase(S.find({Pos[i], i}));
} else {
G.insert({Pos[i], i}); //old pos as considered in jump
stray[i] = true;
}
E.erase(E.find({Pos[i], i}));
E.insert({y, i});
S.insert({y, i});
Pos[i] = y;
if (Q%K == 0) {
for (auto i: S) {
stray[i.second] = 0;
}
G.clear();
S.clear();
makeJump();
}
int at = (*E.begin()).second, prev_at = -1, Ans = 0;
while (at != N) {
if (stray[at]) {
Ans+=1;
at = Next(Pos[at]);
} else {
auto itG = G.upper_bound({Pos[at]+L,MAXN}) ;
auto itS = S.upper_bound({Pos[at]+L,MAXN}) ;
if (itG == G.end() && itS == S.end()) {
for (int i = LOG; i >= 0; i--) {
if (nxt[at][i] != N) {
at = nxt[at][i];
Ans += (1<<i);
}
}
Ans+=1;
//Jump 1 more
//assert(nxt[at][0] == N && at != N);
break;
} else {
int CritPos = 0;
if (itS == S.end() || (itG != G.end() && (*itG).first < (*itS).first)) {
CritPos = (*itG).first;
} else {
CritPos = (*itS).first;
}
for (int i = LOG; i >= 0; i--) {
if (Pos[nxt[at][i]] <= CritPos && !stray[nxt[at][i]]) {
at = nxt[at][i];
Ans += (1<<i);
}
}
Ans+=1;
at = Next(Pos[at]);
}
}
}
return(Ans);
}
Compilation message
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:75:49: warning: unused variable 'prev_at' [-Wunused-variable]
int at = (*E.begin()).second, prev_at = -1, Ans = 0;
^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
