oj.uz

Submission #618674

# Submission time Handle Problem Language Result Execution time Memory
618674 2022-08-02T06:36:06 Z Zanite OGLEDALA (COI15_ogledala) C++17
100 / 100
 2605 ms 201928 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;

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

ll N, M, Q;
ll A[maxN], B[maxN];
vector<Segment> S;

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

	// the lengths of the segments will always be of the pair {p, p-1}

	V.push_back({len+1, 0});
	V.push_back({len, 1});
	for (ll i = 0; i <= 100; i += 2) {
		//cerr << V[i].fi << ' ' << V[i].se << '\n';
		//cerr << V[i+1].fi << ' ' << V[i+1].se << '\n';

		ll Blen = V[i].fi / 2;
		ll Slen = (V[i+1].fi-1) / 2;

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

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

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

		if (!Blen && !Slen) {break;}

		V.push_back({Blen, Bcnt});
		V.push_back({Slen, Scnt});
	}

	// remove the zero-length or zero-count segments at the back
	while (!V.empty() && (!V.back().fi || !V.back().se)) {V.pop_back();}

	// merge the 1-length segments into one vector element
	ll one = 0;
	while (!V.empty() && V.back().fi == 1) {
		one += V.back().se;
		V.pop_back();
	}
	V.push_back({1, one});
}

ll searchSegment(ll L, ll R, ll findLen, ll val) {
	ll M = L + (R-L)/2;
	if (R - L + 1 == findLen) {return M;}

	// find the number of segments of length len
	// in the left part after [L, R] is split
	vector<pll> tmp;
	split(M-L, tmp);

	ll segmentCnt = 0;
	for (auto &[len, cnt] : tmp) {
		if (len == findLen) {segmentCnt += cnt;}
	}

	if (segmentCnt >= val) {
		return searchSegment(L, M-1, findLen, val);
	} else {
		return searchSegment(M+1, R, findLen, val-segmentCnt);
	}
}

int main() {
	scanf("%lld %lld %lld", &M, &N, &Q);

	A[0] = 0, A[N+1] = M+1;
	for (ll i = 1; i <= N; i++) {
		scanf("%lld", &A[i]);
	}
	for (ll i = 1; i <= Q; i++) {
		scanf("%lld", &B[i]);
	}
	B[Q+1] = INF;

	// get a list of segments
	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) continue;
			S.push_back(Segment(len, cnt, i));
		}
	}
	sort(S.begin(), S.end());

	// answer all queries where B[i] <= N
	ll qptr = 1;
	for (; B[qptr] <= N; qptr++) {
		printf("%lld\n", A[B[qptr]]);
	}

	// iterate through S to answer all other queries
	ll cur = N+1;
	for (auto &[len, cnt, initPos] : S) {
		for (; B[qptr] <= cur + cnt - 1; qptr++) {
			printf("%lld\n", searchSegment(A[initPos-1] + 1, A[initPos]-1, len, B[qptr] - cur + 1));
		}
		cur += cnt;
	}
}

Compilation message

ogledala.cpp: In function 'int main()':
ogledala.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%lld %lld %lld", &M, &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ogledala.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%lld", &A[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
ogledala.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   scanf("%lld", &B[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 46 ms 3132 KB Output is correct
4 Correct 37 ms 3136 KB Output is correct
5 Correct 61 ms 9500 KB Output is correct
6 Correct 61 ms 9432 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 632 KB Output is correct
2 Correct 35 ms 648 KB Output is correct
3 Correct 939 ms 200812 KB Output is correct
4 Correct 878 ms 200940 KB Output is correct
5 Correct 1000 ms 201116 KB Output is correct
6 Correct 993 ms 201156 KB Output is correct

Subtask #3
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 102568 KB Output is correct
2 Correct 1077 ms 102616 KB Output is correct
3 Correct 1776 ms 201416 KB Output is correct
4 Correct 1776 ms 201468 KB Output is correct
5 Correct 2605 ms 201928 KB Output is correct
6 Correct 2507 ms 201788 KB Output is correct