Submission #116086

#	Time	Username	Problem	Language	Result	Execution time	Memory
116086		mosesmayer	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	6565 ms	6988 KiB

elephants

#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];
		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++){
		B = i/BLCK;
		blocks[B][SZ[B]++] = tmp[i];
		wbl[tmp[i]] = B;
	}
	for (int B = 0; B < NUMBLOCKS; B++){
		workBlock(B);
	}
}
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;
			if (pos[blocks[i][md]] > x){j = md; ri = md-1;}
			else le = md+1;
		}
		ret += need[blocks[i][j]];
		x = pos[nxt[blocks[i][j]]] + l;
	}
	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;
	}
	for (int B = 0; B < NUMBLOCKS; B++){
		workBlock(B);
	}
}
 
int update(int i, int y){
	int w = wbl[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--;
	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;
	if (++UPDCNTR >= BLCK+5){
		UPDCNTR = 0;
		rebuild();
	}
	return getAns();
}

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