제출 #249250

#제출 시각아이디문제언어결과실행 시간메모리
249250vanicOGLEDALA (COI15_ogledala)C++14
19 / 100
66 ms4084 KiB
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>

using namespace std;

const int maxn=3e5+5;

class Compare{
public:
	bool operator()(pair < int, int > a, pair < int, int > b){
		if(a.first!=b.first){
			return a.first<b.first;
		}
		return a.second>b.second;
	}
};

bool bio[maxn];
priority_queue < pair < int, int >, vector < pair < int, int > >, Compare > svi;
int a[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m, n, q;
	cin >> m >> n >> q;
	for(int i=0; i<n; i++){
		cin >> a[i];
		a[i]--;
		bio[a[i]]=1;
	}
	int br, pos=0;
	bio[m]=1;
	while(pos<m){
		br=0;
		while(!bio[pos]){
			br++;
			pos++;
		}
		if(br){
//			cout << br << " " << pos-br << endl;
			svi.push({br, pos-br});
		}
		pos++;
	}
	int val;
	pos=n;
	pair < int, int > p;
	int b;
	for(int i=0; i<q; i++){
		cin >> b;
		if(b<=pos){
			cout << a[b-1]+1 << '\n';
			continue;
		}
		while(pos<b){
			p=svi.top();
			svi.pop();
			br=p.first;
//			cout << "radim " << p.first << " " << p.second << endl;
			val=p.second+(br-1)/2;
			if(val!=p.second){
				svi.push({val-p.second, p.second});
			}
			if(val!=p.second+br-1){
				svi.push({p.second+br-1-val, val+1});
			}
			pos++;
		}
		cout << val+1 << '\n';
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...