oj.uz

Submission #391768

# Submission time Handle Problem Language Result Execution time Memory
391768 2021-04-19T18:09:58 Z sinamhdv Dancing Elephants (IOI11_elephants) C++11
100 / 100
 8939 ms 12420 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 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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1198 ms 1952 KB Output is correct
8 Correct 1244 ms 2104 KB Output is correct
9 Correct 1093 ms 3120 KB Output is correct
10 Correct 778 ms 3124 KB Output is correct
11 Correct 801 ms 3140 KB Output is correct
12 Correct 1693 ms 3128 KB Output is correct
13 Correct 790 ms 3128 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1198 ms 1952 KB Output is correct
8 Correct 1244 ms 2104 KB Output is correct
9 Correct 1093 ms 3120 KB Output is correct
10 Correct 778 ms 3124 KB Output is correct
11 Correct 801 ms 3140 KB Output is correct
12 Correct 1693 ms 3128 KB Output is correct
13 Correct 790 ms 3128 KB Output is correct
14 Correct 1014 ms 2348 KB Output is correct
15 Correct 1415 ms 2528 KB Output is correct
16 Correct 2853 ms 3396 KB Output is correct
17 Correct 2845 ms 3980 KB Output is correct
18 Correct 3031 ms 3988 KB Output is correct
19 Correct 2402 ms 4036 KB Output is correct
20 Correct 2826 ms 3984 KB Output is correct
21 Correct 2698 ms 3988 KB Output is correct
22 Correct 1284 ms 3908 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1198 ms 1952 KB Output is correct
8 Correct 1244 ms 2104 KB Output is correct
9 Correct 1093 ms 3120 KB Output is correct
10 Correct 778 ms 3124 KB Output is correct
11 Correct 801 ms 3140 KB Output is correct
12 Correct 1693 ms 3128 KB Output is correct
13 Correct 790 ms 3128 KB Output is correct
14 Correct 1014 ms 2348 KB Output is correct
15 Correct 1415 ms 2528 KB Output is correct
16 Correct 2853 ms 3396 KB Output is correct
17 Correct 2845 ms 3980 KB Output is correct
18 Correct 3031 ms 3988 KB Output is correct
19 Correct 2402 ms 4036 KB Output is correct
20 Correct 2826 ms 3984 KB Output is correct
21 Correct 2698 ms 3988 KB Output is correct
22 Correct 1284 ms 3908 KB Output is correct
23 Correct 6153 ms 7404 KB Output is correct
24 Correct 6820 ms 12420 KB Output is correct
25 Correct 5410 ms 12420 KB Output is correct
26 Correct 4959 ms 12420 KB Output is correct
27 Correct 7345 ms 12276 KB Output is correct
28 Correct 4246 ms 5800 KB Output is correct
29 Correct 4201 ms 5808 KB Output is correct
30 Correct 4201 ms 5804 KB Output is correct
31 Correct 4131 ms 5804 KB Output is correct
32 Correct 4542 ms 11856 KB Output is correct
33 Correct 3110 ms 11184 KB Output is correct
34 Correct 4457 ms 12064 KB Output is correct
35 Correct 3106 ms 12356 KB Output is correct
36 Correct 2039 ms 11840 KB Output is correct
37 Correct 7208 ms 12244 KB Output is correct
38 Correct 4689 ms 11072 KB Output is correct
39 Correct 6920 ms 12096 KB Output is correct
40 Correct 4845 ms 11092 KB Output is correct
41 Correct 8897 ms 11848 KB Output is correct
42 Correct 8939 ms 12076 KB Output is correct