oj.uz

Submission #116072

# Submission time Handle Problem Language Result Execution time Memory
116072 2019-06-10T11:06:20 Z mosesmayer Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 12100 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;
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; 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]]];
	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){
		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.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 811 ms 1452 KB Output is correct
8 Correct 769 ms 1536 KB Output is correct
9 Correct 868 ms 2936 KB Output is correct
10 Correct 1053 ms 2808 KB Output is correct
11 Correct 821 ms 2816 KB Output is correct
12 Correct 1543 ms 2680 KB Output is correct
13 Correct 1208 ms 2808 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 811 ms 1452 KB Output is correct
8 Correct 769 ms 1536 KB Output is correct
9 Correct 868 ms 2936 KB Output is correct
10 Correct 1053 ms 2808 KB Output is correct
11 Correct 821 ms 2816 KB Output is correct
12 Correct 1543 ms 2680 KB Output is correct
13 Correct 1208 ms 2808 KB Output is correct
14 Correct 1075 ms 1884 KB Output is correct
15 Correct 1148 ms 2072 KB Output is correct
16 Correct 2361 ms 3064 KB Output is correct
17 Correct 2610 ms 3720 KB Output is correct
18 Correct 3066 ms 3600 KB Output is correct
19 Correct 1503 ms 3728 KB Output is correct
20 Correct 2435 ms 3832 KB Output is correct
21 Correct 2473 ms 3724 KB Output is correct
22 Correct 2001 ms 3704 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 811 ms 1452 KB Output is correct
8 Correct 769 ms 1536 KB Output is correct
9 Correct 868 ms 2936 KB Output is correct
10 Correct 1053 ms 2808 KB Output is correct
11 Correct 821 ms 2816 KB Output is correct
12 Correct 1543 ms 2680 KB Output is correct
13 Correct 1208 ms 2808 KB Output is correct
14 Correct 1075 ms 1884 KB Output is correct
15 Correct 1148 ms 2072 KB Output is correct
16 Correct 2361 ms 3064 KB Output is correct
17 Correct 2610 ms 3720 KB Output is correct
18 Correct 3066 ms 3600 KB Output is correct
19 Correct 1503 ms 3728 KB Output is correct
20 Correct 2435 ms 3832 KB Output is correct
21 Correct 2473 ms 3724 KB Output is correct
22 Correct 2001 ms 3704 KB Output is correct
23 Correct 6488 ms 7468 KB Output is correct
24 Correct 6618 ms 7464 KB Output is correct
25 Correct 5828 ms 7416 KB Output is correct
26 Correct 6624 ms 7472 KB Output is correct
27 Correct 5898 ms 7420 KB Output is correct
28 Correct 4105 ms 2344 KB Output is correct
29 Correct 4154 ms 2336 KB Output is correct
30 Correct 4070 ms 2424 KB Output is correct
31 Correct 4180 ms 2296 KB Output is correct
32 Correct 4993 ms 7460 KB Output is correct
33 Correct 4117 ms 7472 KB Output is correct
34 Correct 6209 ms 7472 KB Output is correct
35 Correct 4206 ms 7472 KB Output is correct
36 Correct 5253 ms 7532 KB Output is correct
37 Correct 8221 ms 7468 KB Output is correct
38 Correct 6554 ms 7544 KB Output is correct
39 Correct 5293 ms 7416 KB Output is correct
40 Correct 8742 ms 7460 KB Output is correct
41 Correct 8917 ms 7584 KB Output is correct
42 Execution timed out 9052 ms 12100 KB Time limit exceeded