Submission #619292

#	Time	Username	Problem	Language	Result	Execution time	Memory
619292		MetalPower	OGLEDALA (COI15_ogledala)	C++14	0 / 100	186 ms	57516 KiB

ogledala

#include <bits/stdc++.h>
using namespace std;

const int MX = 3e5 + 10;

#define ll long long

// Split segment based on A array (call them A segment), view them as if they are disjoint

// The only time where a segment affects another is only when finding which A segment a lady will go to

	// We will then split segments together in each A segment

	// Observe that there will be only O(logMAX) splits
	// And for each split there will only be at most 2 values, X and X+1

struct pli{
	ll fi, se;
	bool operator < (const pli& b) const{
		return fi < b.fi || (fi == b.fi && se > b.se);
	}
};

set<pli> s;

ll M; int N, Q;
ll arr[MX], ans[MX];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

	s.insert({arr[0] - 1, 1});
	for(int i = 0; i < N - 1; i++) s.insert({arr[i + 1] - arr[i] - 1, arr[i] + 1});
	s.insert({M - arr[N - 1], arr[N - 1] + 1});

	int idx = 1;
	while(idx < MX && !s.empty()){
		set<pli>::iterator it = s.end(); it--;
		ll fv = ((*it).fi - 1) / 2, sv = ((*it).fi) / 2;
		ll stf = (*it).se, sts = (*it).se + fv + 1;
		ans[idx++] = stf + fv;
		s.erase(it);
		if(fv > 0) s.insert({fv, stf});
		if(sv > 0) s.insert({sv, sts});
	}

	for(int i = 0; i < Q; i++){
		ll x; cin >> x;
		cout << ans[x] << '\n';
	}
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59