oj.uz

Submission #391706

# Submission time Handle Problem Language Result Execution time Memory
391706 2021-04-19T15:11:18 Z sinamhdv Dancing Elephants (IOI11_elephants) C++11
97 / 100
 9000 ms 11924 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;

bool cmp(int x, int y)
{
	return pos[x] < pos[y];
}


void prep_dp(int b)
{
	for (int i = (int)blk[b].size() - 1; i >= 0; i--)
	{
		int nxt = pos[blk[b][i]] + L;
		if (nxt >= pos[blk[b].back()])
			dp[blk[b][i]] = {1, nxt};
		else
		{
			pos[MAXN - 1] = nxt;
			int u = *upper_bound(all(blk[b]), MAXN - 1, cmp);
			dp[blk[b][i]] = dp[u];
			dp[blk[b][i]].fr++;
		}
	}
}

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, (n - 1) / SQ + 1) prep_dp(i);
}

void init(int N, int L, int X[])
{
	n = N;
	::L = L;
	copy(X, X + n, pos);
	iota(ind, ind + n, 0);
	rebuild();
}

inline int blocklb(int x)
{
	int l = -1, r = (n-1)/SQ;
	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 = (n-1)/SQ;
	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 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2684 ms 1516 KB Output is correct
8 Correct 2899 ms 2640 KB Output is correct
9 Correct 3254 ms 4112 KB Output is correct
10 Correct 3891 ms 3892 KB Output is correct
11 Correct 3202 ms 3832 KB Output is correct
12 Correct 4275 ms 3896 KB Output is correct
13 Correct 3717 ms 3680 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2684 ms 1516 KB Output is correct
8 Correct 2899 ms 2640 KB Output is correct
9 Correct 3254 ms 4112 KB Output is correct
10 Correct 3891 ms 3892 KB Output is correct
11 Correct 3202 ms 3832 KB Output is correct
12 Correct 4275 ms 3896 KB Output is correct
13 Correct 3717 ms 3680 KB Output is correct
14 Correct 2163 ms 3376 KB Output is correct
15 Correct 4030 ms 3336 KB Output is correct
16 Correct 5719 ms 4596 KB Output is correct
17 Correct 7636 ms 5476 KB Output is correct
18 Correct 7562 ms 5408 KB Output is correct
19 Correct 7591 ms 5612 KB Output is correct
20 Correct 7188 ms 5464 KB Output is correct
21 Correct 7378 ms 5448 KB Output is correct
22 Correct 6709 ms 5040 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2684 ms 1516 KB Output is correct
8 Correct 2899 ms 2640 KB Output is correct
9 Correct 3254 ms 4112 KB Output is correct
10 Correct 3891 ms 3892 KB Output is correct
11 Correct 3202 ms 3832 KB Output is correct
12 Correct 4275 ms 3896 KB Output is correct
13 Correct 3717 ms 3680 KB Output is correct
14 Correct 2163 ms 3376 KB Output is correct
15 Correct 4030 ms 3336 KB Output is correct
16 Correct 5719 ms 4596 KB Output is correct
17 Correct 7636 ms 5476 KB Output is correct
18 Correct 7562 ms 5408 KB Output is correct
19 Correct 7591 ms 5612 KB Output is correct
20 Correct 7188 ms 5464 KB Output is correct
21 Correct 7378 ms 5448 KB Output is correct
22 Correct 6709 ms 5040 KB Output is correct
23 Execution timed out 9096 ms 11924 KB Time limit exceeded
24 Halted 0 ms 0 KB -