oj.uz

Submission #391758

# Submission time Handle Problem Language Result Execution time Memory
391758 2021-04-19T17:00:08 Z sinamhdv Dancing Elephants (IOI11_elephants) C++11
50 / 100
 5703 ms 4308 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 270
#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)
{
	int ptr = 0;
	FOR(i, 0, BLK)
	{
		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 (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 1812 ms 2508 KB Output is correct
8 Correct 1938 ms 2636 KB Output is correct
9 Correct 2713 ms 3520 KB Output is correct
10 Correct 2142 ms 3452 KB Output is correct
11 Correct 1544 ms 3520 KB Output is correct
12 Correct 3152 ms 3528 KB Output is correct
13 Correct 2181 ms 3524 KB Output is correct

Subtask #4
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 1812 ms 2508 KB Output is correct
8 Correct 1938 ms 2636 KB Output is correct
9 Correct 2713 ms 3520 KB Output is correct
10 Correct 2142 ms 3452 KB Output is correct
11 Correct 1544 ms 3520 KB Output is correct
12 Correct 3152 ms 3528 KB Output is correct
13 Correct 2181 ms 3524 KB Output is correct
14 Correct 1506 ms 2872 KB Output is correct
15 Correct 2957 ms 3024 KB Output is correct
16 Correct 4543 ms 3752 KB Output is correct
17 Correct 5663 ms 4308 KB Output is correct
18 Correct 5703 ms 4300 KB Output is correct
19 Incorrect 43 ms 4196 KB Output isn't correct
20 Halted 0 ms 0 KB -

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 1812 ms 2508 KB Output is correct
8 Correct 1938 ms 2636 KB Output is correct
9 Correct 2713 ms 3520 KB Output is correct
10 Correct 2142 ms 3452 KB Output is correct
11 Correct 1544 ms 3520 KB Output is correct
12 Correct 3152 ms 3528 KB Output is correct
13 Correct 2181 ms 3524 KB Output is correct
14 Correct 1506 ms 2872 KB Output is correct
15 Correct 2957 ms 3024 KB Output is correct
16 Correct 4543 ms 3752 KB Output is correct
17 Correct 5663 ms 4308 KB Output is correct
18 Correct 5703 ms 4300 KB Output is correct
19 Incorrect 43 ms 4196 KB Output isn't correct
20 Halted 0 ms 0 KB -