oj.uz

답안 #116069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116069 2019-06-10T10:23:18 Z mosesmayer 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 9560 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 + 50){
		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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 0 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 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 0 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 724 ms 1784 KB Output is correct
8 Correct 755 ms 2168 KB Output is correct
9 Correct 771 ms 3280 KB Output is correct
10 Correct 1083 ms 3268 KB Output is correct
11 Correct 794 ms 3348 KB Output is correct
12 Correct 1447 ms 3260 KB Output is correct
13 Correct 1332 ms 3292 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 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 0 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 724 ms 1784 KB Output is correct
8 Correct 755 ms 2168 KB Output is correct
9 Correct 771 ms 3280 KB Output is correct
10 Correct 1083 ms 3268 KB Output is correct
11 Correct 794 ms 3348 KB Output is correct
12 Correct 1447 ms 3260 KB Output is correct
13 Correct 1332 ms 3292 KB Output is correct
14 Correct 972 ms 2360 KB Output is correct
15 Correct 1081 ms 2436 KB Output is correct
16 Correct 2380 ms 3568 KB Output is correct
17 Correct 2515 ms 4672 KB Output is correct
18 Correct 2759 ms 4592 KB Output is correct
19 Correct 1555 ms 4664 KB Output is correct
20 Correct 2462 ms 4524 KB Output is correct
21 Correct 2510 ms 4540 KB Output is correct
22 Correct 2070 ms 4440 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 0 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 724 ms 1784 KB Output is correct
8 Correct 755 ms 2168 KB Output is correct
9 Correct 771 ms 3280 KB Output is correct
10 Correct 1083 ms 3268 KB Output is correct
11 Correct 794 ms 3348 KB Output is correct
12 Correct 1447 ms 3260 KB Output is correct
13 Correct 1332 ms 3292 KB Output is correct
14 Correct 972 ms 2360 KB Output is correct
15 Correct 1081 ms 2436 KB Output is correct
16 Correct 2380 ms 3568 KB Output is correct
17 Correct 2515 ms 4672 KB Output is correct
18 Correct 2759 ms 4592 KB Output is correct
19 Correct 1555 ms 4664 KB Output is correct
20 Correct 2462 ms 4524 KB Output is correct
21 Correct 2510 ms 4540 KB Output is correct
22 Correct 2070 ms 4440 KB Output is correct
23 Correct 6012 ms 9008 KB Output is correct
24 Correct 6620 ms 8884 KB Output is correct
25 Correct 5489 ms 9040 KB Output is correct
26 Correct 6508 ms 8912 KB Output is correct
27 Correct 6380 ms 8988 KB Output is correct
28 Correct 4350 ms 2296 KB Output is correct
29 Correct 4520 ms 2524 KB Output is correct
30 Correct 4351 ms 2388 KB Output is correct
31 Correct 4494 ms 2552 KB Output is correct
32 Correct 4744 ms 8956 KB Output is correct
33 Correct 4290 ms 9060 KB Output is correct
34 Correct 6295 ms 8936 KB Output is correct
35 Correct 4264 ms 9480 KB Output is correct
36 Correct 5049 ms 9028 KB Output is correct
37 Correct 7808 ms 9560 KB Output is correct
38 Correct 7045 ms 8964 KB Output is correct
39 Correct 5745 ms 9040 KB Output is correct
40 Correct 7116 ms 9016 KB Output is correct
41 Execution timed out 9038 ms 9028 KB Time limit exceeded
42 Halted 0 ms 0 KB -