제출 #116080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116080		mosesmayer	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	7093 ms	7168 KiB

elephants

#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 = sz; 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;
	//	}
		while (pos[blocks[B][j]] - pos[blocks[B][i]] > l) j--;
		j++;
		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();
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3