oj.uz

Submission #618212

# Submission time Handle Problem Language Result Execution time Memory
618212 2022-08-02T03:11:13 Z logTheorist OGLEDALA (COI15_ogledala) C++17
19 / 100
 4000 ms 199764 KB 
#include <bits/stdc++.h>
using namespace std;

using ll	= long long;
using pll	= pair<ll, ll>;

#define fi	first
#define se	second

const int maxN	= 1e5 + 5;

const ll INF	= 1e18;

ll M, N, Q;
ll A[maxN], B[maxN];

struct Segment {
	ll len, cnt, initPos;

	Segment(ll len, ll cnt, ll initPos) :
		len(len), cnt(cnt), initPos(initPos)
	{}

	bool operator < (const Segment &other) const {
		return make_pair(-len, initPos) < make_pair(-other.len, other.initPos);
	}
};

void split(ll len, vector<pll> &V) {
	if (len == 0) return;

	// all possible lengths can form pairs of {p, p-1}
	V.push_back({len+1, 0});
	V.push_back({len, 1});

	for (ll ptr = 0; ; ptr += 2) {
		ll big = V[ptr].fi / 2;
		ll small = (V[ptr+1].fi - 1) / 2;

		//cout << V[ptr].fi << ' ' << V[ptr].se << '\n';
		//cout << V[ptr+1].fi << ' ' << V[ptr+1].se << '\n';

		ll Bcnt = V[ptr].se, Scnt = V[ptr+1].se;

		if ((V[ptr].fi - 1) / 2 == big) {
			Bcnt += V[ptr].se;
		} else {
			Scnt += V[ptr].se;
		}
		if (V[ptr+1].fi / 2 == big) {
			Bcnt += V[ptr+1].se;
		} else {
			Scnt += V[ptr+1].se;
		}

		V.push_back({big, Bcnt});
		V.push_back({small, Scnt});

		if (big == 0 && small == 0) break;
	}

	while (!V.empty() && (!V.back().fi || !V.back().se)) V.pop_back();
	ll one = 0;
	while (!V.empty() && (V.back().fi == 1)) {
		one += V.back().se;
		V.pop_back();
	}
	if (one) V.push_back({1, one});

	//for (auto &[len, cnt] : V) {cout << len << ' ' << cnt << '\n';}
}

ll findPos(ll findLen, ll l, ll r, ll val) {
	cerr << "findPos(" << findLen << ", " << l << ", " << r << ", " << val << ")\n";
	if (r - l + 1 == findLen) {return l + (r-l)/2;}

	vector<pll> tmp;
	ll m = l + (r-l)/2;
	split(m-l, tmp);
	ll findCnt = 0;
	for (auto &[len, cnt] : tmp) {
		if (len == findLen) {findCnt += cnt; break;}
	}
	cerr << findCnt << '\n';

	if (val <= findCnt) {
		return findPos(findLen, l, m-1, val);
	} else {
		return findPos(findLen, m+1, r, val-findCnt);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> M >> N >> Q;
	A[0] = 0, A[N+1] = M+1;
	for (ll i = 1; i <= N; i++) {
		cin >> A[i];
	}
	vector<Segment> S;
	for (ll i = 1; i <= N+1; i++) {
		vector<pll> tmp;
		split(A[i] - A[i-1] - 1, tmp);
		for (auto &[len, cnt] : tmp) {
			if (len && cnt) S.push_back(Segment(len, cnt, i));
		}
	}
	sort(S.begin(), S.end());
	for (auto &[len, cnt, idx] : S) {
		cerr << len << ' ' << cnt << ' ' << idx << '\n';
	}

	for (ll i = 1; i <= Q; i++) {
		cin >> B[i];
	}
	B[Q+1] = INF;
	
	ll qptr = 1;
	for (; B[qptr] <= N; qptr++) {
		cout << A[B[qptr]] << '\n';
	}
	ll cur = N+1;
	for (auto &[len, cnt, idx] : S) {
		//cout << "! " << cur << '\n';
		for (; B[qptr] <= cur + cnt - 1; qptr++) {
			cout << findPos(len, A[idx-1]+1, A[idx]-1, B[qptr] - cur + 1) << '\n';
		}
		cur += cnt;
	}
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 340 KB Output is correct
2 Correct 19 ms 388 KB Output is correct
3 Correct 3246 ms 10420 KB Output is correct
4 Correct 2591 ms 8936 KB Output is correct
5 Correct 2675 ms 12700 KB Output is correct
6 Correct 2445 ms 12780 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 3076 KB Output is correct
2 Correct 752 ms 3068 KB Output is correct
3 Execution timed out 4043 ms 199764 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4058 ms 100976 KB Time limit exceeded
2 Halted 0 ms 0 KB -