oj.uz

Submission #116065

# Submission time Handle Problem Language Result Execution time Memory
116065 2019-06-10T10:05:20 Z mosesmayer Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 14512 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];
const int DMY = 15e4 + 5;

inline void workBlock(int B){
	int sz = blocks[B].size();
	if (!sz) return;
	pos[DMY] = pos[blocks[B].back()] + l + 135;
	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; 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]]];
	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 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
}
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);
	}
	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];
	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 > pos[blocks[B].back()]) 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
		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){
		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++)
                   ~~^~~~~~~~~~~~~~~~~~

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 2 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
24.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 2 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 Correct 733 ms 2564 KB Output is correct
8 Correct 759 ms 3072 KB Output is correct
9 Correct 839 ms 4792 KB Output is correct
10 Correct 1045 ms 4580 KB Output is correct
11 Correct 808 ms 4680 KB Output is correct
12 Correct 1479 ms 4736 KB Output is correct
13 Correct 1251 ms 4348 KB Output is correct

Subtask #4
47.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 2 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 Correct 733 ms 2564 KB Output is correct
8 Correct 759 ms 3072 KB Output is correct
9 Correct 839 ms 4792 KB Output is correct
10 Correct 1045 ms 4580 KB Output is correct
11 Correct 808 ms 4680 KB Output is correct
12 Correct 1479 ms 4736 KB Output is correct
13 Correct 1251 ms 4348 KB Output is correct
14 Correct 1000 ms 3692 KB Output is correct
15 Correct 1086 ms 3748 KB Output is correct
16 Correct 2230 ms 5440 KB Output is correct
17 Correct 2481 ms 6616 KB Output is correct
18 Correct 2785 ms 6572 KB Output is correct
19 Correct 1575 ms 6844 KB Output is correct
20 Correct 2490 ms 6668 KB Output is correct
21 Correct 2509 ms 6632 KB Output is correct
22 Correct 1975 ms 6072 KB Output is correct

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 2 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 Correct 733 ms 2564 KB Output is correct
8 Correct 759 ms 3072 KB Output is correct
9 Correct 839 ms 4792 KB Output is correct
10 Correct 1045 ms 4580 KB Output is correct
11 Correct 808 ms 4680 KB Output is correct
12 Correct 1479 ms 4736 KB Output is correct
13 Correct 1251 ms 4348 KB Output is correct
14 Correct 1000 ms 3692 KB Output is correct
15 Correct 1086 ms 3748 KB Output is correct
16 Correct 2230 ms 5440 KB Output is correct
17 Correct 2481 ms 6616 KB Output is correct
18 Correct 2785 ms 6572 KB Output is correct
19 Correct 1575 ms 6844 KB Output is correct
20 Correct 2490 ms 6668 KB Output is correct
21 Correct 2509 ms 6632 KB Output is correct
22 Correct 1975 ms 6072 KB Output is correct
23 Correct 6054 ms 13992 KB Output is correct
24 Correct 6871 ms 14056 KB Output is correct
25 Correct 5624 ms 14084 KB Output is correct
26 Correct 6668 ms 14008 KB Output is correct
27 Correct 6237 ms 13896 KB Output is correct
28 Correct 4424 ms 5324 KB Output is correct
29 Correct 4556 ms 5452 KB Output is correct
30 Correct 4456 ms 5240 KB Output is correct
31 Correct 4519 ms 5368 KB Output is correct
32 Correct 5090 ms 13420 KB Output is correct
33 Correct 4671 ms 12768 KB Output is correct
34 Correct 6552 ms 13668 KB Output is correct
35 Correct 4350 ms 14508 KB Output is correct
36 Correct 5244 ms 13448 KB Output is correct
37 Correct 8546 ms 14512 KB Output is correct
38 Correct 7213 ms 12672 KB Output is correct
39 Correct 5685 ms 13620 KB Output is correct
40 Correct 7122 ms 12608 KB Output is correct
41 Execution timed out 9047 ms 13376 KB Time limit exceeded
42 Halted 0 ms 0 KB -