Submission #618989

#	Time	Username	Problem	Language	Result	Execution time	Memory
618989		sentheta	OGLEDALA (COI15_ogledala)	C++17	41 / 100	344 ms	44760 KiB

ogledala

#include<algorithm>
#include<iostream>
#include<cassert>
#include<vector>
#include<string>
#include<array>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;

#define V vector
#define Int long long
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define nl '\n'
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define all(x) (x).begin(), (x).end()

#define int long long
const int N = 3e5+5;

int m, n, q;

// {len, -l, r}
set<array<int,3>> s;
void insert(int l,int r){
	s.insert({r-l+1, -l, r});
}

int ans[N];

signed main(){

	cin >> m >> n >> q;

	V<int> taken;
	rep(i,1,n+1){
		int x;
		cin >> x;

		ans[i] = x;
		taken.push_back(x);
	}
	
	sort(all(taken));
	if(1<taken[0]){
		insert(1,taken[0]-1);
	}
	if(taken.back()<m){
		insert(taken.back()+1,m);
	}
	rep(i,0,n-1){
		insert(taken[i]+1,taken[i+1]-1);
	}


	rep(i,n+1,min(N,m+1)){
		auto[len,l,r] = *prev(s.end());
		l *= -1;
		s.erase(prev(s.end()));

		int mid;
		if(len&1) mid = l+len/2;
		else mid = l+len/2-1;

		ans[i] = mid;

		if(l<mid) insert(l,mid-1);
		if(mid<r) insert(mid+1,r);
	}

	while(q--){
		int i;
		cin >> i;

		cout << ans[i] << nl;
	}

	
}

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