oj.uz

Submission #77002

# Submission time Handle Problem Language Result Execution time Memory
77002 2018-09-20T02:09:36 Z shoemakerjo Dancing Elephants (IOI11_elephants) C++14
100 / 100
 6598 ms 116436 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;
#define maxn 150010

const int bucket = 390;

int n;
int l;
int pos[maxn];
int bstart[bucket];
int numneed[maxn];
int lastcov[maxn];
int mybuck[maxn];

vector<vector<int>> comp(bucket);

void printout();
void reconstruct();

void init(int N, int L, int X[])
{
 	n = N;
 	l = L;
 	for (int i = 0; i < bucket; i++) comp[i].clear();
 	for (int i = 0; i < n; i++) {
 		comp[i/bucket].push_back(i);
 		pos[i] = X[i];
 	}
 	fill(bstart, bstart+bucket, 1234567890);
 	reconstruct();

 	// cout << "start printout :: " << endl;
 	printout();
// 
 	// cout << endl;
 	// fill(bstart, bstart+bucket, 1234567890);
}

vector<int> sorted;


void calccomp(int i) {
	if (comp[i].size() == 0) return;

 	int curend = comp[i].size();
 	int vv = comp[i][curend-1];
 	numneed[vv] = 1;
 	lastcov[vv] = pos[vv] + l;

 	for (int j = comp[i].size()-2; j >= 0; j--) {
 		vv = comp[i][j];
 		while (curend > 0 && pos[comp[i][curend-1]] - 
 			pos[vv] > l) {
 			--curend; 
 			// cout << "DECREMENTED CUREND" << endl;
 		}

 		if (curend == comp[i].size()) {
 			numneed[vv] = 1;
 			lastcov[vv] = pos[vv]+l;
 		}
 		else {
 			numneed[vv] = 1 + numneed[comp[i][curend]];
 			lastcov[vv] = lastcov[comp[i][curend]];
 		}
 	}
}

void reconstruct() {
	sorted.clear();
	for (int i = 0; i < bucket; i++) {
		for (int vv : comp[i]) {
			sorted.push_back(vv);
		}
	}
	// cout << "recon size: " << sorted.size() << endl;
	for (int i = 0; i < bucket; i++) comp[i].clear();
	for (int i = 0; i < n; i++) {
		// cout << "recon thing: " << sorted[i] << endl;
		if (i% bucket == 0) {
			bstart[i/bucket] = pos[sorted[i]];
		}
		comp[i/bucket].push_back(sorted[i]);
		mybuck[sorted[i]] = i/bucket;
	}

	for (int i = 0; i < bucket; i++) {
 		calccomp(i);
 	}
 	bstart[0] = -1;
}



int query() {
	//just go
	int ans = 0;
	int start;
	for (int i = 0; i < bucket; i++) {
		if (comp[i].size() == 0) continue;
		start = i;
		break;
	}
	ans = numneed[comp[start][0]];
	int cend = lastcov[comp[start][0]];
	for (int i = start+1; i < bucket; i++) {
		if (comp[i].size() == 0) continue;

		// cout << i << " ::: " << cend << endl;

		if (cend >= pos[comp[i][comp[i].size()-1]]) {
			// cout << "CONTINUED" << endl;
			continue;
		}

		int lo = 0;
		int hi = comp[i].size()-1;
		while (lo < hi) {
			int mid = (lo+hi)/2;
			if (pos[comp[i][mid]] <= cend) {
				lo = mid+1;
			}
			else hi = mid;
		}
		// cout << "lo:     " << lo << endl;
		ans += numneed[comp[i][lo]];
		cend = lastcov[comp[i][lo]];
	}
	printout();
	// cout << "answering: " << ans << endl;
	// cout << endl;
	return ans;

}

void printout() {
	return;
	for (int i = 0; i < bucket; i++) {
		for (int v : comp[i]) {
			cout << v << " : " << pos[v] <<
			 " (bucket " << i << ")" << 
			 " num needed: " << numneed[v] <<  endl;
		}
	}

}

int ct = 0;

int update(int i, int y)
{
	int obuck = mybuck[i];
	for (int j = 0; j < comp[obuck].size(); j++) {
		if (comp[obuck][j] == i) {
			comp[obuck].erase(comp[obuck].begin() + j);
			break;
		}
	}
	calccomp(obuck);

	// cout << "intermediate printout" << endl;
	// printout();
	// cout << endl;

	int nbuck = 0;
	for (int j = 0; j < bucket; j++) {
		if (y >= bstart[j]) nbuck = j;
		else break;
	}
	bool added = false;
	for (int j = 0; j < comp[nbuck].size(); j++) {
		// cout << "looking at " << comp[nbuck][j] << endl;
		if (y < pos[comp[nbuck][j]]) {
			// cout << "said " << y << " is less than " << 
				// pos[comp[nbuck][j]] << endl;
			comp[nbuck].insert(comp[nbuck].begin() + j, i);
			added = true;
			break;
		}
	}
	if (!added){
		// cout << "did not add for " << i << " to " << y << endl;
		comp[nbuck].push_back(i);
	}

	pos[i] = y;
	calccomp(nbuck);
	mybuck[i] = nbuck;



	ct++;
	if (ct%bucket == 0){
		// cout << "what " << endl;
		// printout();
		// cout << endl;
		// cout << "THING: " << bstart[1] << endl;
		reconstruct();
	}
	return query();
}

Compilation message

elephants.cpp: In function 'void calccomp(int)':
elephants.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (curend == comp[i].size()) {
        ~~~~~~~^~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:155:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < comp[obuck].size(); j++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp:173:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < comp[nbuck].size(); j++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int query()':
elephants.cpp:100:6: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int start;
      ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 317 ms 1732 KB Output is correct
8 Correct 349 ms 2760 KB Output is correct
9 Correct 542 ms 5452 KB Output is correct
10 Correct 465 ms 6708 KB Output is correct
11 Correct 406 ms 7984 KB Output is correct
12 Correct 968 ms 9392 KB Output is correct
13 Correct 649 ms 10560 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 317 ms 1732 KB Output is correct
8 Correct 349 ms 2760 KB Output is correct
9 Correct 542 ms 5452 KB Output is correct
10 Correct 465 ms 6708 KB Output is correct
11 Correct 406 ms 7984 KB Output is correct
12 Correct 968 ms 9392 KB Output is correct
13 Correct 649 ms 10560 KB Output is correct
14 Correct 393 ms 11344 KB Output is correct
15 Correct 558 ms 12992 KB Output is correct
16 Correct 1555 ms 15600 KB Output is correct
17 Correct 1756 ms 18136 KB Output is correct
18 Correct 1833 ms 20220 KB Output is correct
19 Correct 972 ms 22452 KB Output is correct
20 Correct 1813 ms 24496 KB Output is correct
21 Correct 1727 ms 26516 KB Output is correct
22 Correct 883 ms 28020 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 317 ms 1732 KB Output is correct
8 Correct 349 ms 2760 KB Output is correct
9 Correct 542 ms 5452 KB Output is correct
10 Correct 465 ms 6708 KB Output is correct
11 Correct 406 ms 7984 KB Output is correct
12 Correct 968 ms 9392 KB Output is correct
13 Correct 649 ms 10560 KB Output is correct
14 Correct 393 ms 11344 KB Output is correct
15 Correct 558 ms 12992 KB Output is correct
16 Correct 1555 ms 15600 KB Output is correct
17 Correct 1756 ms 18136 KB Output is correct
18 Correct 1833 ms 20220 KB Output is correct
19 Correct 972 ms 22452 KB Output is correct
20 Correct 1813 ms 24496 KB Output is correct
21 Correct 1727 ms 26516 KB Output is correct
22 Correct 883 ms 28020 KB Output is correct
23 Correct 4737 ms 36344 KB Output is correct
24 Correct 4932 ms 41360 KB Output is correct
25 Correct 4396 ms 46384 KB Output is correct
26 Correct 4473 ms 51404 KB Output is correct
27 Correct 4524 ms 56276 KB Output is correct
28 Correct 1918 ms 56276 KB Output is correct
29 Correct 1799 ms 57920 KB Output is correct
30 Correct 1908 ms 60856 KB Output is correct
31 Correct 1802 ms 63876 KB Output is correct
32 Correct 3800 ms 72448 KB Output is correct
33 Correct 2687 ms 76396 KB Output is correct
34 Correct 4138 ms 80952 KB Output is correct
35 Correct 2594 ms 85880 KB Output is correct
36 Correct 2438 ms 90464 KB Output is correct
37 Correct 6108 ms 96068 KB Output is correct
38 Correct 4160 ms 98996 KB Output is correct
39 Correct 4033 ms 103572 KB Output is correct
40 Correct 4132 ms 107256 KB Output is correct
41 Correct 6598 ms 111720 KB Output is correct
42 Correct 6484 ms 116436 KB Output is correct