Submission #77002

#	Time	Username	Problem	Language	Result	Execution time	Memory
77002		shoemakerjo	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	6598 ms	116436 KiB

elephants

#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 (stderr)

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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3