oj.uz

Submission #391753

# Submission time Handle Problem Language Result Execution time Memory
391753 2021-04-19T16:43:32 Z sinamhdv Dancing Elephants (IOI11_elephants) C++11
97 / 100
 9000 ms 7364 KB 
// 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 400
#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)
{
	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
		{
			pos[MAXN - 1] = nxt;
			int nu = *upper_bound(all(blk[b]), MAXN - 1, cmp);
			dp[u] = dp[nu];
			dp[u].fr++;
		}
	}
}

inline void rebuild(void)
{
	FOR(i, 0, BLK) blk[i].clear();
	sort(ind, ind + n, cmp);
	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 (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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 2448 ms 2636 KB Output is correct
8 Correct 2601 ms 2632 KB Output is correct
9 Correct 3123 ms 3532 KB Output is correct
10 Correct 3507 ms 3524 KB Output is correct
11 Correct 2960 ms 3652 KB Output is correct
12 Correct 3941 ms 3524 KB Output is correct
13 Correct 3431 ms 3524 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 2448 ms 2636 KB Output is correct
8 Correct 2601 ms 2632 KB Output is correct
9 Correct 3123 ms 3532 KB Output is correct
10 Correct 3507 ms 3524 KB Output is correct
11 Correct 2960 ms 3652 KB Output is correct
12 Correct 3941 ms 3524 KB Output is correct
13 Correct 3431 ms 3524 KB Output is correct
14 Correct 1994 ms 2860 KB Output is correct
15 Correct 3787 ms 3020 KB Output is correct
16 Correct 5384 ms 3752 KB Output is correct
17 Correct 6829 ms 4300 KB Output is correct
18 Correct 6954 ms 4300 KB Output is correct
19 Correct 7221 ms 4296 KB Output is correct
20 Correct 6841 ms 4416 KB Output is correct
21 Correct 6989 ms 4300 KB Output is correct
22 Correct 6298 ms 4304 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 2448 ms 2636 KB Output is correct
8 Correct 2601 ms 2632 KB Output is correct
9 Correct 3123 ms 3532 KB Output is correct
10 Correct 3507 ms 3524 KB Output is correct
11 Correct 2960 ms 3652 KB Output is correct
12 Correct 3941 ms 3524 KB Output is correct
13 Correct 3431 ms 3524 KB Output is correct
14 Correct 1994 ms 2860 KB Output is correct
15 Correct 3787 ms 3020 KB Output is correct
16 Correct 5384 ms 3752 KB Output is correct
17 Correct 6829 ms 4300 KB Output is correct
18 Correct 6954 ms 4300 KB Output is correct
19 Correct 7221 ms 4296 KB Output is correct
20 Correct 6841 ms 4416 KB Output is correct
21 Correct 6989 ms 4300 KB Output is correct
22 Correct 6298 ms 4304 KB Output is correct
23 Execution timed out 9058 ms 7364 KB Time limit exceeded
24 Halted 0 ms 0 KB -