oj.uz

Submission #684513

# Submission time Handle Problem Language Result Execution time Memory
684513 2023-01-21T11:43:46 Z MetalPower OGLEDALA (COI15_ogledala) C++14
100 / 100
 2188 ms 199704 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<ll, ll>
#define fi first
#define se second
#define ll long long

const ll MX = 1e5 + 10;

struct range{
	ll len, cnt, idx;

	range(ll len, ll cnt, ll idx): len(len), cnt(cnt), idx(idx){}

	// sort by largest len
	bool operator < (const range& other) const{
		return len > other.len || (len == other.len && idx < other.idx);
	}
};

ll N, M, Q; vector<range> vec;
ll A[MX], B[MX];

void build(ll len, ll idx, vector<range>& R){

	// big len, big cnt, small len, small cnt
	ll bl = len + 1, bc = 0, sl = len, sc = 1;
	if(bc != 0) R.push_back({bl, bc, idx});
	if(sc != 0) R.push_back({sl, sc, idx});

	ll one = 0;
	while(bl > 0){
		if(bl % 2 == 0){
			// 4 3 -> (1 2) (1 1)
			// 6 5 -> (2 3) (2 2)
			bl = bl / 2, sl = sl / 2;
			sc = bc + 2 * sc, bc = bc;
		}else if(bl % 2 == 1){
			// 3 2 -> (1 1) (0 1)
			// 5 4 -> (2 2) (1 2)
			bl = bl / 2, sl = (sl - 1) / 2;
			sc = sc, bc = 2 * bc + sc;
		}

		if(bl == 1) one += bc;
		else if(bl != 0 && bc != 0) R.push_back({bl, bc, idx});
		if(sl == 1) one += sc;
		else if(sl != 0 && sc != 0) R.push_back({sl, sc, idx});
	}
	R.push_back({1, one, idx});
}

ll bf(ll lf, ll rg, ll len, ll cnt){
	ll mid = (lf + rg) / 2;
	if((rg - lf + 1) == len) return mid;

	vector<range> C;
	ll curr = 0;
	build(mid - lf, -1, C);
	for(auto x : C)
		if(x.len == len) curr += x.cnt;

	if(cnt <= curr) return bf(lf, mid - 1, len, cnt);
	else return bf(mid + 1, rg, len, cnt - curr);
}

int main(){

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> M >> N >> Q;
	for(ll i = 1; i <= N; i++){
		cin >> A[i];
		build(A[i] - A[i - 1] - 1, i, vec);
	}
	A[N + 1] = M + 1;
	build(A[N + 1] - A[N] - 1, N + 1, vec);

	for(ll i = 1; i <= Q; i++) cin >> B[i];

	ll j = 1;
	for(; j <= Q && B[j] <= N; j++) cout << A[B[j]] << '\n';

	sort(vec.begin(), vec.end());

	ll num = N + 1; // range_no
	for(range x : vec){
		ll len = x.len, cnt = x.cnt, idx = x.idx;
		// cout << "At range " << A[idx - 1] + 1 << " " << A[idx] - 1 << " exists " << cnt << " length of " << len << '\n';
		for(; j <= Q && B[j] < num + cnt; j++){
			// cout << "Binser at " << A[idx - 1] + 1 << " " << A[idx] - 1 << " length of " << len << " number " << B[j] - num + 1 << '\n'; 
			cout << bf(A[idx - 1] + 1, A[idx] - 1, len, B[j] - num + 1) << '\n';
		}
		num += cnt;
	}
}

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 38 ms 3132 KB Output is correct
4 Correct 30 ms 3040 KB Output is correct
5 Correct 63 ms 9272 KB Output is correct
6 Correct 54 ms 8868 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 684 KB Output is correct
2 Correct 28 ms 668 KB Output is correct
3 Correct 764 ms 199476 KB Output is correct
4 Correct 749 ms 199400 KB Output is correct
5 Correct 867 ms 199240 KB Output is correct
6 Correct 865 ms 199192 KB Output is correct

Subtask #3
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 890 ms 100528 KB Output is correct
2 Correct 863 ms 100300 KB Output is correct
3 Correct 1458 ms 199584 KB Output is correct
4 Correct 1450 ms 199704 KB Output is correct
5 Correct 2188 ms 199252 KB Output is correct
6 Correct 2056 ms 199324 KB Output is correct