oj.uz

Submission #391714

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

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 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++;
		}
	}
}

inline 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 332 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 332 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 332 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 6682 ms 1372 KB Output is correct
8 Correct 6745 ms 1748 KB Output is correct
9 Correct 6889 ms 2496 KB Output is correct
10 Correct 6858 ms 2500 KB Output is correct
11 Correct 5895 ms 2628 KB Output is correct
12 Correct 7584 ms 2752 KB Output is correct
13 Correct 6798 ms 2508 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 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 6682 ms 1372 KB Output is correct
8 Correct 6745 ms 1748 KB Output is correct
9 Correct 6889 ms 2496 KB Output is correct
10 Correct 6858 ms 2500 KB Output is correct
11 Correct 5895 ms 2628 KB Output is correct
12 Correct 7584 ms 2752 KB Output is correct
13 Correct 6798 ms 2508 KB Output is correct
14 Correct 5316 ms 1856 KB Output is correct
15 Execution timed out 9097 ms 1868 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 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 6682 ms 1372 KB Output is correct
8 Correct 6745 ms 1748 KB Output is correct
9 Correct 6889 ms 2496 KB Output is correct
10 Correct 6858 ms 2500 KB Output is correct
11 Correct 5895 ms 2628 KB Output is correct
12 Correct 7584 ms 2752 KB Output is correct
13 Correct 6798 ms 2508 KB Output is correct
14 Correct 5316 ms 1856 KB Output is correct
15 Execution timed out 9097 ms 1868 KB Time limit exceeded
16 Halted 0 ms 0 KB -