Submission #391768

#	Time	Username	Problem	Language	Result	Execution time	Memory
391768		sinamhdv	Dancing Elephants (IOI11_elephants)	C++11	100 / 100	8939 ms	12420 KiB

elephants

// IOI11_elephants
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 150100
#define SQ 1000
#define BLK (MAXN / SQ + 10)

int n, L;
vector<int> blk[BLK];
int bnum[MAXN], blkind[MAXN];
int pos[MAXN], ind[MAXN];
pii dp[MAXN];
int qnum;
int bcnt;

inline bool cmp(int x, int y)
{
	return pos[x] < pos[y];
}

inline void prep_dp(int b)
{
	int ptr = blk[b].size() - 1;
	for (int i = (int)blk[b].size() - 1; i >= 0; i--)
	{
		int u = blk[b][i];
		int nxt = pos[u] + L;
		if (nxt >= pos[blk[b].back()])
			dp[u] = {1, nxt};
		else
		{
			while (pos[blk[b][ptr]] > nxt) ptr--;
			dp[u] = dp[blk[b][ptr + 1]];
			dp[u].fr++;
		}
	}
}

inline void rebuild(void)
{
	int ptr = 0;
	FOR(i, 0, bcnt)
	{
		for (int u : blk[i]) ind[ptr++] = u;
		blk[i].clear();
	}
	FOR(i, 0, n) blk[i/SQ].pb(ind[i]), bnum[ind[i]] = i/SQ, blkind[ind[i]] = i % SQ;
	FOR(i, 0, bcnt) prep_dp(i);
}

void init(int N, int L, int X[])
{
	n = N;
	::L = L;
	bcnt = (n - 1) / SQ + 1;
	copy(X, X + n, pos);
	iota(ind, ind + n, 0);
	FOR(i, 0, BLK) blk[i].reserve(2 * SQ + 10);
	rebuild();
}

inline int blocklb(int x)
{
	int l = -1, r = bcnt - 1;
	if (blk[r].empty()) r--;
	if (pos[blk[r].back()] < x) return INF;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (pos[blk[mid].back()] < x) l = mid;
		else r = mid;
	}
	return r;
}

inline int person_ub(int x)
{
	int b = blocklb(x + 1);
	if (b >= INF) return INF;
	pos[MAXN - 1] = x;
	return *upper_bound(all(blk[b]), MAXN - 1, cmp);
}

inline void swapadj(int b, int i)
{
	blkind[blk[b][i - 1]]++;
	blkind[blk[b][i]]--;
	swap(blk[b][i], blk[b][i - 1]);
}

int update(int i, int y)
{
	qnum++;
	if (qnum % (SQ - 5) == 0)
		rebuild();

	// update blocks
	int old = bnum[i];
	int nw = blocklb(y);
	if (nw >= INF) nw = bcnt - 1;
	pos[i] = y;
	bnum[i] = nw;

	FOR(j, blkind[i] + 1, (int)blk[old].size()) blkind[blk[old][j]]--;
	
	blk[old].erase(blk[old].begin() + blkind[i]);
	blk[nw].pb(i);
	blkind[i] = blk[nw].size() - 1;
	while (blkind[i] && y < pos[blk[nw][blkind[i] - 1]])
		swapadj(nw, blkind[i]);

	// re-calc dp
	prep_dp(old);
	prep_dp(nw);

	// get answer
	int ans = 0;
	int p = blk[0][0];
	while (p < n)
	{
		ans += dp[p].fr;
		p = person_ub(dp[p].sc);
	}
	
	return ans;
}

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