| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 227469 | spdskatr | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// This problem is cooked
#include "camera.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cassert>
#define fi first
#define se second
#define K 404 // Not found
using namespace std;
typedef pair<int, int> pii;
int N, L, cnt, loc[150005], curblock[150005];
pair<int, int> el[150005];
struct block {
int val[K<<1], pos[K<<1], dp[K<<1], ext[K<<1], sz;
void reset() {
fill(val, val+K, 0);
fill(dp, dp+K, 0);
}
void recalc() {
int rp = sz;
for (int i = sz - 1; i >= 0; i--) {
while (pos[rp-1] > pos[i] + L) rp--;
if (rp == sz) {
dp[i] = 1;
ext[i] = pos[i] + L + 1;
} else {
dp[i] = dp[rp] + 1;
ext[i] = ext[rp];
}
}
}
void remove(int x) {
int lp = 0;
while (val[lp] != x && lp < sz) lp++;
assert(val[lp] == x);
sz--;
while (lp < sz) {
val[lp] = val[lp+1];
pos[lp] = pos[lp+1];
lp++;
}
val[sz] = pos[sz] = 0;
recalc();
}
void insert(int x, int v) {
int lp = 0;
while (lp < sz && pos[lp] < v) lp++;
sz++;
for (int i = sz-1; i > lp; i--) {
val[i] = val[i-1];
pos[i] = pos[i-1];
}
val[lp] = x, pos[lp] = v;
recalc();
}
} sd[505];
void init(int n, int l, int X[])
{
N = n, L = l;
for (int i = 0; i < N; i++) loc[i] = X[i];
for (int b = 0; b * K < N; b++) {
for (int j = 0; j < min(K, N-b*K); j++) {
int actual = b*K+j;
sd[b].val[j] = actual;
sd[b].pos[j] = loc[actual];
curblock[actual] = b;
}
sd[b].sz = min(K, N-b*K);
sd[b].recalc();
}
}
int update(int ind, int y)
{
loc[ind] = y;
if (cnt >= K - 1) {
// Recalculate everything
for (int i = 0; i < N; i++) el[i] = { loc[i], i };
sort(el, el+N);
for (int b = 0; b*K < N; b++) {
sd[b].reset();
for (int j = 0; j < min(K, N-b*K); j++) {
int actual = b*K + j;
sd[b].val[j] = el[actual].se;
sd[b].pos[j] = el[actual].fi;
curblock[el[actual].se] = b;
}
sd[b].sz = min(K, N-b*K);
sd[b].recalc();
}
cnt = 0;
} else {
int b2 = 0;
sd[curblock[ind]].remove(ind);
while ((b2 + 1) * K < N && sd[b2+1].sz > 0 && sd[b2+1].pos[0] < loc[ind]) {
b2++;
}
curblock[ind] = b2;
sd[b2].insert(ind, loc[ind]);
}
int curpt = 0, tot = 0;
for (int b = 0; (b+1)*K < N || (b*K < N && sd[b].sz > 0); b++) {
if (sd[b].pos[sd[b].sz-1] >= curpt) {
int lo = 0, hi = sd[b].sz;
if (sd[b].pos[0] >= curpt) hi = 0;
else while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (sd[b].pos[mid] < curpt) lo = mid;
else hi = mid;
}
tot += sd[b].dp[hi];
curpt = sd[b].ext[hi];
assert(curpt > sd[b].pos[sd[b].sz-1]);
}
}
cnt++;
return tot;
}