Submission #152663

#	Time	Username	Problem	Language	Result	Execution time	Memory
152663		qkxwsm	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	7587 ms	19140 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 150013
#define INF 1000000007
#define MAGIC 1700

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, L, Q, B;
int arr[MAXN];
multiset<int> vals;
vector<array<int, 3> > stor[MAGIC];
int ans;

//ok keep blocks of size k.
//each block stores: this guy takes x cost to jump to the end. and he arrives at y.
//ok so each query takes O(k) + O(N/k logN)
//so you choose k = sqrt(NlogN)
//so rebuild every sqrt(NlogN). each rebuild takes O(N). solution in Nsqrt(NlogN)

void calc(int i)
{
	int iter = SZ(stor[i]) - 1;
	FORD(j, SZ(stor[i]), 0)
	{
		int x = stor[i][j][0];
		while(iter >= 0 && stor[i][iter][0] >= x + L) iter--;
		if (iter == SZ(stor[i]) - 1)
		{
			stor[i][j][1] = 1;
			stor[i][j][2] = x + L;
		}
		else
		{
			stor[i][j][1] = 1 + stor[i][iter + 1][1];
			stor[i][j][2] = stor[i][iter + 1][2];
		}
	}
}
void del(int v)
{
	//find which block has it.
	FORD(i, B, 0)
	{
		if (stor[i][0][0] > v) continue;
		//there's something that has x.
		FOR(j, 0, SZ(stor[i]))
		{
			if (stor[i][j][0] == v)
			{
				stor[i].erase(stor[i].begin() + j);
				break;
			}
		}
		calc(i);
		break;
	}
}
void ins(int v)
{
	FORD(i, B, 0)
	{
		if (stor[i][0][0] > v && i != 0) continue;
		FOR(j, 0, SZ(stor[i]) + 1)
		{
			if (j == SZ(stor[i]) || stor[i][j][0] > v)
			{
				stor[i].insert(stor[i].begin() + j, {v, 0, 0});
				break;
			}
		}
		calc(i);
		break;
	}
}
void build()
{
	auto it = vals.begin();
	FOR(i, 0, B)
	{
		stor[i].clear();
		FOR(j, 0, MAGIC)
		{
			if (it == vals.end()) break;
			stor[i].PB({*it, 0, 0});
			it++;
		}
		calc(i);
	}
	return;
}
void debug()
{
	FOR(i, 0, B)
	{
		cerr << "BLOCK " << i << endl;
		FOR(j, 0, SZ(stor[i]))
		{
			FOR(k, 0, 3)
			{
				cerr << stor[i][j][k] << ' ';
			}
			cerr << endl;
		}
	}
}
int trav()
{
	int res = 0, pos = -INF;
	FOR(i, 0, B)
	{
		//find the first guy that's > pos.
		array<int, 3> tmp = {pos, -1, -1};
		int idx = LB(ALL(stor[i]), tmp) - stor[i].begin();
		if (idx == SZ(stor[i])) continue;
		res += stor[i][idx][1];
		pos = stor[i][idx][2];
	}
	return res;
}
void init(int n, int l, int x[])
{
	N = n; L = l; B = (N + MAGIC - 1) / MAGIC;
	L++;
	FOR(i, 0, N)
	{
		arr[i] = x[i];
		vals.insert(arr[i]);
	}
	build();
}
int update(int idx, int v)
{
	vals.erase(vals.find(arr[idx]));
	del(arr[idx]);
	arr[idx] = v;
	vals.insert(arr[idx]);
	ins(arr[idx]);
	Q++;
	if (Q % MAGIC == 0)
	{
		build();
	}
	// debug();
	// if (Q >= 17000)
	// {
	// 	cerr << "Q = " << Q << endl;
	// 	debug();
	// }
	// cerr << "Q = " << Q << endl;
	// debug();
	ans = trav();
	return ans;
}

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