Submission #251112

#	Time	Username	Problem	Language	Result	Execution time	Memory
251112		kostia244	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	26 / 100	26 ms	2296 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 170170, C = 804;
int n, l, x[maxn], bl[maxn], to[maxn], sto[maxn], w[maxn];
vector<int> b[maxn/C];
int lower_bound(int X) {
	int B = 0, I = 0;
	for(int z = 1<<9; z>>=1;) if(!b[B+z].empty() && x[b[B+z][0]] < X) B += z;
	for(int z = 1<<9; z>>=1;) if(I+z < b[B].size() && x[b[B][I+z]] < X) I += z;
	//cout << X << " // " << B << " " << I << '\n';
	if(x[b[B][I]] < X && ++I == b[B].size()) I = 0, ++B;
	//cout << X << " // " << B << " " << I << '\n';
	//cout << "Final" << (b[B].empty() ? n : b[B][I]) << '\n';
	return b[B].empty() ? n : b[B][I];
}
void update(int i) {
	//cout << "Updated block " << i << "\n";
	for(auto v : b[i])
		to[v] = lower_bound(x[v]+l+1);//, cout << v << " " << x[v]+l+1 << " " << to[v] << '\n';
	for(int v, _v = b[i].size(); _v--;) {
		v = b[i][_v];
		if(bl[to[v]] == bl[v])
			sto[v] = sto[to[v]], w[v] = 1+w[to[v]];
		else sto[v] = to[v], w[v] = 1;
	}
}
void pop(int v) {
	for(int i = 0; i+1 < b[bl[v]].size(); i++)
		if(b[bl[v]][i] == v) swap(b[bl[v]][i], b[bl[v]][i+1]);
	b[bl[v]].pop_back();
	update(bl[v]);
}
void push(int i) {
	bl[i] = min((n-1)/C, bl[lower_bound(x[i])]);
	int bid = bl[i];
	//for(auto &b : b[bid]) cout << x[b] << " "; cout << "F\n";
	for(auto &b : b[bid])
		if(x[b] > x[i]) swap(b, i);
	b[bid].push_back(i);
	//for(auto &b : b[bid]) cout << x[b] << " "; cout << "G\n";
	update(bid);
}
void build() {
	vector<int> ord;
	ord.reserve(n);
	for(int i = 0; i*C < n; i++)
		for(auto j : b[i])
			ord.push_back(j);
	if(ord.empty())
		for(int i = 0; i < n; i++) ord.push_back(i);
	
	for(int i = 0; i*C < n; i++) {
		b[i].clear();
		b[i].reserve(2*C);
	}
	for(int i, pos = 0; pos < n; pos++) {
		i = ord[pos];
		bl[i] = pos/C;
		b[bl[i]].push_back(i);
	}
	for(int i = 0; i*C < n; i++) update(i);
}
void init(int N, int L, int X[]) {
	n = N;
	l = L;
	bl[n] = maxn;
	for(int i = 0; i < n; i++) x[i] = X[i];
	build();
}
int calc() {
	int p = b[0][0], ans = 0;
	while(p != n) ans += w[p], p = sto[p];
	return ans;
}
int timer = 0;
int update(int i, int y) {
	pop(i);
	//for(int uwu = 0; uwu < 2; uwu++, cout << " | ")
	//	for(auto i : b[uwu]) cout << x[i] << " ";cout << ":\n";
	//cout << "x_" << i << " := " << y << endl;
	x[i] = y;
	push(i);
	//for(int uwu = 0; uwu < 2; uwu++, cout << " | ")
	//	for(auto i : b[uwu]) cout << x[i] << " ";cout << ":\n";
	if(++timer == C-1) timer = 0, build();
	return calc();
}

Compilation message (stderr)

elephants.cpp: In function 'int lower_bound(int)':
elephants.cpp:10:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int z = 1<<9; z>>=1;) if(I+z < b[B].size() && x[b[B][I+z]] < X) I += z;
                               ~~~~^~~~~~~~~~~~~
elephants.cpp:12:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(x[b[B][I]] < X && ++I == b[B].size()) I = 0, ++B;
                       ~~~~^~~~~~~~~~~~~~
elephants.cpp: In function 'void pop(int)':
elephants.cpp:29:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i+1 < b[bl[v]].size(); i++)
                 ~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3