oj.uz

Submission #116068

# Submission time Handle Problem Language Result Execution time Memory
116068 2019-06-10T10:18:18 Z mosesmayer Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 10156 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();
}
inline 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
}
inline 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 256 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 256 KB Output is correct
7 Correct 725 ms 2168 KB Output is correct
8 Correct 764 ms 2380 KB Output is correct
9 Correct 821 ms 3632 KB Output is correct
10 Correct 1092 ms 3736 KB Output is correct
11 Correct 801 ms 3580 KB Output is correct
12 Correct 1516 ms 3780 KB Output is correct
13 Correct 1217 ms 3636 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 256 KB Output is correct
7 Correct 725 ms 2168 KB Output is correct
8 Correct 764 ms 2380 KB Output is correct
9 Correct 821 ms 3632 KB Output is correct
10 Correct 1092 ms 3736 KB Output is correct
11 Correct 801 ms 3580 KB Output is correct
12 Correct 1516 ms 3780 KB Output is correct
13 Correct 1217 ms 3636 KB Output is correct
14 Correct 945 ms 2764 KB Output is correct
15 Correct 1097 ms 2844 KB Output is correct
16 Correct 2295 ms 3976 KB Output is correct
17 Correct 2554 ms 4984 KB Output is correct
18 Correct 2774 ms 4952 KB Output is correct
19 Correct 1490 ms 4876 KB Output is correct
20 Correct 2488 ms 5064 KB Output is correct
21 Correct 2913 ms 4948 KB Output is correct
22 Correct 2129 ms 5024 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 256 KB Output is correct
7 Correct 725 ms 2168 KB Output is correct
8 Correct 764 ms 2380 KB Output is correct
9 Correct 821 ms 3632 KB Output is correct
10 Correct 1092 ms 3736 KB Output is correct
11 Correct 801 ms 3580 KB Output is correct
12 Correct 1516 ms 3780 KB Output is correct
13 Correct 1217 ms 3636 KB Output is correct
14 Correct 945 ms 2764 KB Output is correct
15 Correct 1097 ms 2844 KB Output is correct
16 Correct 2295 ms 3976 KB Output is correct
17 Correct 2554 ms 4984 KB Output is correct
18 Correct 2774 ms 4952 KB Output is correct
19 Correct 1490 ms 4876 KB Output is correct
20 Correct 2488 ms 5064 KB Output is correct
21 Correct 2913 ms 4948 KB Output is correct
22 Correct 2129 ms 5024 KB Output is correct
23 Correct 6158 ms 9368 KB Output is correct
24 Correct 7131 ms 9388 KB Output is correct
25 Correct 5753 ms 9400 KB Output is correct
26 Correct 6748 ms 9388 KB Output is correct
27 Correct 6325 ms 9416 KB Output is correct
28 Correct 4310 ms 2796 KB Output is correct
29 Correct 4921 ms 2840 KB Output is correct
30 Correct 4500 ms 2680 KB Output is correct
31 Correct 4499 ms 2780 KB Output is correct
32 Correct 5114 ms 9380 KB Output is correct
33 Correct 4363 ms 9404 KB Output is correct
34 Correct 6517 ms 9352 KB Output is correct
35 Correct 4586 ms 10156 KB Output is correct
36 Correct 5493 ms 9440 KB Output is correct
37 Correct 8941 ms 10096 KB Output is correct
38 Correct 7462 ms 9324 KB Output is correct
39 Correct 5597 ms 9284 KB Output is correct
40 Correct 7267 ms 9288 KB Output is correct
41 Execution timed out 9036 ms 9428 KB Time limit exceeded
42 Halted 0 ms 0 KB -