oj.uz

Submission #391767

# Submission time Handle Problem Language Result Execution time Memory
391767 2021-04-19T18:08:15 Z sinamhdv Dancing Elephants (IOI11_elephants) C++11
50 / 100
 9000 ms 4356 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 100
#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 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1568 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1568 KB Output is correct
4 Correct 1 ms 1612 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 831 ms 2548 KB Output is correct
8 Correct 1199 ms 2684 KB Output is correct
9 Correct 3342 ms 3580 KB Output is correct
10 Correct 3348 ms 3652 KB Output is correct
11 Correct 1976 ms 3576 KB Output is correct
12 Correct 4033 ms 3652 KB Output is correct
13 Correct 3396 ms 3580 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1568 KB Output is correct
4 Correct 1 ms 1612 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 831 ms 2548 KB Output is correct
8 Correct 1199 ms 2684 KB Output is correct
9 Correct 3342 ms 3580 KB Output is correct
10 Correct 3348 ms 3652 KB Output is correct
11 Correct 1976 ms 3576 KB Output is correct
12 Correct 4033 ms 3652 KB Output is correct
13 Correct 3396 ms 3580 KB Output is correct
14 Correct 937 ms 2924 KB Output is correct
15 Correct 2199 ms 3084 KB Output is correct
16 Correct 5743 ms 3816 KB Output is correct
17 Correct 8886 ms 4356 KB Output is correct
18 Execution timed out 9093 ms 4300 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Correct 1 ms 1612 KB Output is correct
3 Correct 1 ms 1568 KB Output is correct
4 Correct 1 ms 1612 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct
7 Correct 831 ms 2548 KB Output is correct
8 Correct 1199 ms 2684 KB Output is correct
9 Correct 3342 ms 3580 KB Output is correct
10 Correct 3348 ms 3652 KB Output is correct
11 Correct 1976 ms 3576 KB Output is correct
12 Correct 4033 ms 3652 KB Output is correct
13 Correct 3396 ms 3580 KB Output is correct
14 Correct 937 ms 2924 KB Output is correct
15 Correct 2199 ms 3084 KB Output is correct
16 Correct 5743 ms 3816 KB Output is correct
17 Correct 8886 ms 4356 KB Output is correct
18 Execution timed out 9093 ms 4300 KB Time limit exceeded
19 Halted 0 ms 0 KB -