oj.uz

Submission #393980

# Submission time Handle Problem Language Result Execution time Memory
393980 2021-04-25T06:13:22 Z sinamhdv Dancing Elephants (IOI11_elephants) C++11
100 / 100
 5980 ms 12440 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)
{
	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 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 = 0; for (; nw < bcnt; nw++) if (pos[blk[nw].back()] >= y) break;
	if (nw == bcnt) nw--;
	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 p = -1;
	int ans = 0;
	FOR(b, 0, bcnt)
	{
		pos[MAXN - 1] = p;
		auto l = upper_bound(all(blk[b]), MAXN - 1, cmp);
		if (l == blk[b].end()) continue;
		ans += dp[*l].fr;
		p = dp[*l].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 1 ms 1484 KB Output is correct
5 Correct 1 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 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 518 ms 2644 KB Output is correct
8 Correct 561 ms 2676 KB Output is correct
9 Correct 593 ms 3648 KB Output is correct
10 Correct 461 ms 3660 KB Output is correct
11 Correct 466 ms 3644 KB Output is correct
12 Correct 884 ms 3664 KB Output is correct
13 Correct 437 ms 3660 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 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 518 ms 2644 KB Output is correct
8 Correct 561 ms 2676 KB Output is correct
9 Correct 593 ms 3648 KB Output is correct
10 Correct 461 ms 3660 KB Output is correct
11 Correct 466 ms 3644 KB Output is correct
12 Correct 884 ms 3664 KB Output is correct
13 Correct 437 ms 3660 KB Output is correct
14 Correct 513 ms 2992 KB Output is correct
15 Correct 710 ms 4440 KB Output is correct
16 Correct 1441 ms 5572 KB Output is correct
17 Correct 1565 ms 6332 KB Output is correct
18 Correct 1675 ms 6244 KB Output is correct
19 Correct 1215 ms 6476 KB Output is correct
20 Correct 1572 ms 6332 KB Output is correct
21 Correct 1526 ms 6300 KB Output is correct
22 Correct 764 ms 5896 KB Output is correct

Subtask #5
3.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 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 518 ms 2644 KB Output is correct
8 Correct 561 ms 2676 KB Output is correct
9 Correct 593 ms 3648 KB Output is correct
10 Correct 461 ms 3660 KB Output is correct
11 Correct 466 ms 3644 KB Output is correct
12 Correct 884 ms 3664 KB Output is correct
13 Correct 437 ms 3660 KB Output is correct
14 Correct 513 ms 2992 KB Output is correct
15 Correct 710 ms 4440 KB Output is correct
16 Correct 1441 ms 5572 KB Output is correct
17 Correct 1565 ms 6332 KB Output is correct
18 Correct 1675 ms 6244 KB Output is correct
19 Correct 1215 ms 6476 KB Output is correct
20 Correct 1572 ms 6332 KB Output is correct
21 Correct 1526 ms 6300 KB Output is correct
22 Correct 764 ms 5896 KB Output is correct
23 Correct 4777 ms 12428 KB Output is correct
24 Correct 5109 ms 12440 KB Output is correct
25 Correct 4209 ms 12436 KB Output is correct
26 Correct 4257 ms 12440 KB Output is correct
27 Correct 5029 ms 12296 KB Output is correct
28 Correct 1833 ms 6372 KB Output is correct
29 Correct 1782 ms 6384 KB Output is correct
30 Correct 1838 ms 6380 KB Output is correct
31 Correct 1916 ms 6312 KB Output is correct
32 Correct 3501 ms 11992 KB Output is correct
33 Correct 3247 ms 11196 KB Output is correct
34 Correct 3584 ms 12080 KB Output is correct
35 Correct 3347 ms 12372 KB Output is correct
36 Correct 3051 ms 11852 KB Output is correct
37 Correct 5142 ms 12264 KB Output is correct
38 Correct 3353 ms 11044 KB Output is correct
39 Correct 4449 ms 12116 KB Output is correct
40 Correct 3500 ms 11108 KB Output is correct
41 Correct 5933 ms 11860 KB Output is correct
42 Correct 5980 ms 12100 KB Output is correct