oj.uz

Submission #116039

# Submission time Handle Problem Language Result Execution time Memory
116039 2019-06-10T09:07:26 Z mosesmayer Dancing Elephants (IOI11_elephants) C++17
26 / 100
 17 ms 2296 KB 
#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;
vi blocks[BLCK+10];
int need[mxsz], nxt[mxsz];
int ans[BLCK+10];
const int DMY = 15e4 + 2;

inline void workBlock(int B){
	int sz = blocks[B].size();
	if (!sz) return;
	pos[DMY] = pos[blocks[B].back()] + l + 1;
	blocks[B].push_back(DMY);
	nxt[DMY] = DMY;
	for (int i = sz-1, j; i >= 0; --i){
		int u = blocks[B][i];
		int le = i, ri = sz, md;
		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] = nxt[v];
	}
	for (int i = 0; i < sz; i++)
		if (nxt[blocks[B][i]] == DMY) nxt[blocks[B][i]] = blocks[B][i];
	blocks[B].pop_back();
}
void rebuild(){
	vi tmp;
	for (int B = 0; B < NUMBLOCKS; B++){
		for (int i = 0; i < blocks[B].size(); i++)
			tmp.pb(blocks[B][i]);
		blocks[B].clear();
	}
	for (int i = 0; i < n; i++){
		//Printf( "%d%c", tmp[i], " \n"[i+1==n]);
		blocks[i/BLCK].pb(tmp[i]);
		wbl[tmp[i]] = i/BLCK;
		ord[tmp[i]] = i;
	}
	for (int i = 0; i < NUMBLOCKS; i++){
		workBlock(i);
	}
#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]);
	}
#endif
}
int getAns(){
	int x = -1; // next needed to cover
	int ret = 0;
	for (int i = 0; i < NUMBLOCKS; i++){
		if (blocks[i].empty()) continue;
		if (pos[blocks[i].back()] <= x) continue;
		int le = 0, ri = blocks[i].size() - 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);
	}
	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];
	for (int i = 0; i < n; i++) blocks[0].pb(i);
	NUMBLOCKS = ((n-1)/BLCK) + 1;
	rebuild();
}

int update(int i, int y){
	int w = wbl[i];
	blocks[w].erase(find(blocks[w].begin(), blocks[w].end(), i));
	workBlock(w);
	pos[i] = y;
	w = 0;
	for (int B = 0; B < NUMBLOCKS; B++){
		if (blocks[B].empty()) w++;
		else if (y >= blocks[B][0]) w++;
		else break;
	}
	if (w >= NUMBLOCKS) w--;
	Printf( "new block %d\n", w);
	int idx = blocks[w].size();
	blocks[w].pb(i);
	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
	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
	if (++UPDCNTR >= BLCK){
		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();
}

Compilation message

elephants.cpp: In function 'void rebuild()':
elephants.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < blocks[B].size(); i++)
                   ~~^~~~~~~~~~~~~~~~~~
elephants.cpp:43:22: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int v = blocks[B][j];
                      ^
elephants.cpp:35:21: note: 'j' was declared here
  for (int i = sz-1, j; i >= 0; --i){
                     ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:43:22: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int v = blocks[B][j];
                      ^
elephants.cpp:35:21: note: 'j' was declared here
  for (int i = sz-1, j; i >= 0; --i){
                     ^
elephants.cpp:43:22: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int v = blocks[B][j];
                      ^
elephants.cpp:35:21: note: 'j' was declared here
  for (int i = sz-1, j; i >= 0; --i){
                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 17 ms 2296 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 17 ms 2296 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 17 ms 2296 KB Output isn't correct
8 Halted 0 ms 0 KB -