oj.uz

Submission #77001

# Submission time Handle Problem Language Result Execution time Memory
77001 2018-09-20T01:49:34 Z shoemakerjo Dancing Elephants (IOI11_elephants) C++14
26 / 100
 22 ms 2896 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];
 	}

 	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;
		if (cend >= comp[i][comp[i].size()-1]) continue;

		int lo = 0;
		int hi = comp[i].size()-1;
		while (lo < hi) {
			int mid = (lo+hi)/2;
			if (comp[i][mid] <= cend) {
				lo = mid+1;
			}
			else hi = mid;
		}
		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) comp[nbuck].push_back(i);

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

	ct++;
	if (ct%bucket == 0) 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:148:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < comp[obuck].size(); j++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
elephants.cpp:166: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 508 KB Output is correct
3 Correct 2 ms 588 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 508 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 712 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 2 ms 784 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 712 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 2 ms 784 KB Output is correct
7 Incorrect 22 ms 2896 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 712 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 2 ms 784 KB Output is correct
7 Incorrect 22 ms 2896 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 712 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 2 ms 784 KB Output is correct
7 Incorrect 22 ms 2896 KB Output isn't correct
8 Halted 0 ms 0 KB -