| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 116073 | mosesmayer | 코끼리 (Dancing Elephants) (IOI11_elephants) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#define nDEBUG
#ifdef DEBUG
#define Printf(...) fprintf(stderr, __VA_ARGS__)
#else
#define Printf(...)
#endif
#include "elephants.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
typedef vector<int> vi;
const int BLCK = 400; // sqrt n
int UPDCNTR = 0;
const int mxsz = 15e4 + 14;
int n;
LL l;
int pos[mxsz], //ord[mxsz];
int wbl[mxsz]; // stores wbl block elephant i is in
int NUMBLOCKS;
int blocks[BLCK+10][2 * BLCK + 15];
int need[mxsz], nxt[mxsz];
int SZ[BLCK+10];
const int DMY = 15e4 + 5;
inline void workBlock(int B){
int sz = SZ[B];
if (!sz) return;
pos[DMY] = pos[blocks[B][sz-1]] + l + 1;
blocks[B][SZ[B]++] = DMY;
nxt[DMY] = DMY;
for (int i = sz-1, j; i >= 0; --i){
int u = blocks[B][i];
int le = i, ri = sz, md; j = sz;
while (le <= ri){
md = (le + ri) >> 1;
if (pos[blocks[B][md]] - pos[u] > l){j = md; ri = md-1;}
else le = md+1;
}
int v = blocks[B][j];
need[u] = need[v] + 1;
nxt[u] = v;
}
for (int i = sz-1; i >= 0; --i)
if (nxt[blocks[B][i]] == DMY) nxt[blocks[B][i]] = blocks[B][i];
else nxt[blocks[B][i]] = nxt[nxt[blocks[B][i]]];
SZ[B]--;
}
int tmp[mxsz];
inline void rebuild(){
int now = 0;
for (int B = 0; B < NUMBLOCKS; B++){
for (int i = 0; i < SZ[B]; i++)
tmp[now++] = blocks[B][i];
SZ[B] = 0;
}
for (int i = 0, B; i < n; i++){
// Printf( "%d%c", tmp[i], " \n"[i+1==n]);
B = i/BLCK;
blocks[B][SZ[B]++] = tmp[i];
wbl[tmp[i]] = B;
//ord[tmp[i]] = i;
}
for (int B = 0; B < NUMBLOCKS; B++){
workBlock(B);
}
#ifdef DEBUG
for (int i = 0; i < n; i++){
Printf( "%d: o_%d p_%d w_%d nd:%d nx:%d\n",
i, ord[i],pos[i],wbl[i],need[i], nxt[i]);
}
Printf("end rebuild\n");
#endif
}
inline int getAns(){
int x = -1; // next needed to cover
int ret = 0;
for (int i = 0; i < NUMBLOCKS; i++){
if (!SZ[i]) continue;
if (pos[blocks[i][SZ[i]-1]] <= x) continue;
int le = 0, ri = SZ[i] - 1, md, j = 0;
while (le <= ri){
md = (le + ri) >> 1;
// Printf( "%d %d %d\n", le, ri, md);
if (pos[blocks[i][md]] > x){j = md; ri = md-1;}
else le = md+1;
}
// Printf( "cur ret: %d x: %d b:%d nd:%d nxt:%d pos:%d\n",
// ret, x, blocks[i][j], need[blocks[i][j]],
// nxt[blocks[i][j]], pos[nxt[blocks[i][j]]]);
// Printf( "L :: %d\n", l);
ret += need[blocks[i][j]];
x = pos[nxt[blocks[i][j]]] + l;
// Printf( "new ret: %d x: %d\n", ret, x);
}
// Printf("END OF QUERY\n\n\n\n");
return ret;
}
void init(int N, int L, int X[]){
n = N; l = L;
for (int i = 0; i < n; i++) pos[i] = X[i];
NUMBLOCKS = ((n-1)/BLCK) + 1;
for (int i = 0, B; i < n; i++){
B = i/BLCK;
blocks[B][SZ[B]++] = i;
wbl[i] = B;
//ord[i] = i;
}
for (int B = 0; B < NUMBLOCKS; B++){
workBlock(B);
}
}
int update(int i, int y){
int w = wbl[i];
//blocks[w].erase(find(blocks[w].begin(), blocks[w].end(), i));
for (int p = 0; p < SZ[w]; p++){
if (blocks[w][p] == i){
for (int j = p; j < SZ[w] - 1; j++){
blocks[w][j] = blocks[w][j+1];
}
SZ[w]--; break;
}
}
workBlock(w);
pos[i] = y;
w = 0;
for (int B = 0; B < NUMBLOCKS; B++){
if (!SZ[B]) w++;
else if (y > pos[blocks[B][SZ[B]-1]]) w++;
else break;
}
if (w >= NUMBLOCKS) w--;
// Printf( "new block %d\n", w);
int idx = SZ[w];
blocks[w][idx] = i; SZ[w]++;
while (idx > 0 && pos[blocks[w][idx]] < pos[blocks[w][idx-1]]){
swap(blocks[w][idx], blocks[w][idx - 1]); idx--;
}
workBlock(w);
wbl[i] = w;
#ifdef DEBUG
Printf("post update\n");
for (int i = 0; i < n; i++){
Printf( "%d: o_%d p_%d w_%d nd:%d nx:%d\n",
i, ord[i],pos[i],wbl[i],need[i], nxt[i]);
}
fputs("\n", stderr);
for (int B = 0; B < NUMBLOCKS; B++){
for (int i : blocks[B]) Printf( "%d ", i);
}
fputs("\n", stderr);
Printf("end update\n\n");
#endif
if (++UPDCNTR >= BLCK+5){
UPDCNTR = 0;
rebuild();
#ifdef DEBUG
Printf( " REBUILD\n");
for (int i = 0; i < n; i++){
Printf( "%d: o_%d p_%d w_%d nd:%d nx:%d\n",
i, ord[i],pos[i],wbl[i],need[i], nxt[i]);
}
fputs("\n", stderr);
for (int B = 0; B < NUMBLOCKS; B++){
for (int i : blocks[B]) Printf( "%d ", i);
fputs("\n", stderr);
}
#endif
}
return getAns();
}