oj.uz

Submission #619205

# Submission time Handle Problem Language Result Execution time Memory
619205 2022-08-02T10:30:54 Z Drew_ OGLEDALA (COI15_ogledala) C++17
19 / 100
 2261 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
#define size(x) (int)x.size()

#define int long long

using ii = pair<int, int>;
using ll = long long;
using pl = pair<ll, ll>;

const int MAX = 1e5 + 69;
const ll inf = 1e18 + 69;

ll M, N, Q;
ll A[MAX], B[MAX], Blen[MAX], Bpos[MAX], Bblank[MAX];
ll ans[MAX];

int32_t main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> M >> N >> Q;
	for (int i = 1; i <= N; ++i)
		cin >> A[i];

	int si = 1;
	for (int i = 1; i <= Q; ++i)
	{
		cin >> B[i];
		if (B[i] <= N)
			ans[i] = A[B[i]], si++;
		B[i] -= N;
	}
	A[0] = 0; A[N+1] = M+1;

	vector<pl> len;
	for (int i = 0; i <= N; ++i) if (A[i+1] - A[i] - 1)
		len.pb({A[i+1] - A[i] - 1, A[i] + 1});

	map<ll, ll> fq;
	priority_queue<ll> pq;
	for (auto [l, x] : len)
	{
		if (!fq.count(l))
			pq.push(l);
		fq[l]++;
	}

	const auto genfq = [&]()
	{
		while (!pq.empty())
		{
			ll val = pq.top(); pq.pop();
		
			if ((val-1) >> 1)
			{
				if (!fq.count((val-1) >> 1))
					pq.push((val-1) >> 1);
				fq[(val-1) >> 1] += fq[val];
			}
			if (val >> 1)
			{
				if (!fq.count(val >> 1))
					pq.push(val >> 1);
				fq[val >> 1] += fq[val];
			}
		}
	};
	genfq();

	vector<ll> zip;
	for (const auto &[x, y] : fq)
		zip.pb(x);

	// cerr << "zip: ";
	// for (int x : zip)
	// 	cerr << x << ", ";
	// cerr << '\n';

	vector<ii> nxt(size(fq)); // division by 2
	for (int a = 0; a < size(zip); ++a)
	{
		ll L = (zip[a]-1) >> 1, R = (zip[a]) >> 1;
		int i = -1, j = -1;
		if (L > 0) i = (int)(lower_bound(zip.begin(), zip.end(), L) - zip.begin());
		if (R > 0) j = (int)(lower_bound(zip.begin(), zip.end(), R) - zip.begin());
		nxt[a] = { i, j };
	}

	vector<vector<int>> impt(size(zip));
	for (int i = 0; i < size(zip); ++i)
	{
		impt[i].pb(i);
		if (nxt[i].f1 != -1) for (int x : impt[nxt[i].f1])
			impt[i].pb(x);
		if (nxt[i].s2 != -1) for (int x : impt[nxt[i].s2])
			impt[i].pb(x);
		sort(impt[i].begin(), impt[i].end());
		impt[i].resize(unique(impt[i].begin(), impt[i].end()) - impt[i].begin());
	}

	vector<ll> ctr(size(zip));
	vector<queue<pl>> memo(size(zip));
	{
		vector<pl> vec(fq.rbegin(), fq.rend());
		for (int i = 0; i < size(vec); ++i)
			vec[i].f1 = (int)(lower_bound(zip.begin(), zip.end(), vec[i].f1) - zip.begin());
		for (int i = 1; i < size(vec); ++i)
			vec[i].s2 += vec[i-1].s2;

		for (int i = si, j = 0; i <= Q; ++i)
		{
			while (vec[j].s2 < B[i])
				++j;
			Blen[i] = vec[j].f1;
			Bpos[i] = B[i] - (j ? vec[j-1].s2 : 0);
		
			memo[Blen[i]].push({Bpos[i], i});
		}
	}

	vector<ll> freq(size(zip));
	for (int i = 0; i < size(len); ++i)
	{
		auto [l, x] = len[i];

		int id = (int)(lower_bound(zip.begin(), zip.end(), l) - zip.begin());
		for (int j : impt[id])
			freq[j] = 0;
		freq[id] = 1;

		for (int j = size(impt[id]) - 1; j >= 0; --j)
		{
			auto [a, b] = nxt[impt[id][j]];
			if (a != -1)
				freq[a] += freq[impt[id][j]];
			if (b != -1)
				freq[b] += freq[impt[id][j]];
		}

		vector<pl> vec;
		for (int j = size(impt[id]) - 1; j >= 0; --j)
			vec.pb({impt[id][j], freq[impt[id][j]]});

		// there are ~(log MAX) values
		for (auto [x, y] : vec)
		{
			ctr[x] += y;
			while (!memo[x].empty() && memo[x].front().f1 <= ctr[x])
			{
				Bpos[memo[x].front().s2] -= ctr[x] - y;
				Bblank[memo[x].front().s2] = i;
				memo[x].pop();
			}
		}
	}

	for (auto &i : freq)
		i = 0;

	for (int i = si; i <= Q; ++i)
	{
		auto [val, pos] = len[Bblank[i]];
		int id = (lower_bound(zip.begin(), zip.end(), val) - zip.begin());
		// cerr << "\n\n solving: " << i << " " << Blen[i] << " " << Bpos[i] << '\n';
		for (;;)
		{
			// cerr << "id: " << id << " " << pos << '\n';
			if (id == Blen[i])
			{
				ans[i] = pos + (zip[id]-1) / 2;
				break;
			}

			// check to go to left or right
			ll L = nxt[id].f1, R = nxt[id].s2;

			if (L == -1)
			{
				id = R, pos++;
				continue;
			}

			freq[L] = 1;
			for (int j = size(impt[L]) - 1; j >= 0; --j)
			{
				if (impt[L][j] < Blen[i])
					break;

				auto [a, b] = nxt[impt[L][j]];
				if (a >= Blen[i])
					freq[a] += freq[impt[L][j]];
				if (b >= Blen[i])
					freq[b] += freq[impt[L][j]];
			}

			// cerr << "freq: ";
			// for (int i = 0; i < size(zip); ++i)
			// 	cerr << freq[i] << ", ";
			// cerr << '\n';
			// cerr << Bpos[i] << " and " << freq[Blen[i]] << '\n';

			if (Bpos[i] <= freq[Blen[i]]) id = L;
			else id = R, pos += zip[L] + 1, Bpos[i] -= freq[Blen[i]];
		
			for (int j : impt[L])
				freq[j] = 0;
		}
	}

	for (int i = 1; i <= Q; ++i)
		cout << ans[i] << '\n';

	return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 31 ms 5732 KB Output is correct
4 Correct 33 ms 5628 KB Output is correct
5 Correct 38 ms 7580 KB Output is correct
6 Correct 53 ms 7872 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4696 KB Output is correct
2 Correct 20 ms 4928 KB Output is correct
3 Runtime error 2261 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 1133 ms 196716 KB Output is correct
2 Correct 1053 ms 180616 KB Output is correct
3 Runtime error 1844 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -