Submission #104944

#TimeUsernameProblemLanguageResultExecution timeMemory
104944ShtefOGLEDALA (COI15_ogledala)C++14
41 / 100
348 ms45584 KiB
#include <iostream>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;

struct nes{
	ll l, r;
	friend bool operator <(nes x, nes y){
		if(x.r - x.l + 1 == y.r - y.l + 1)
			return x.l < y.l;
		return x.r - x.l + 1 > y.r - y.l + 1;
	}
};

ll m, n, q, a[300005], c[300005];
multiset <nes> s;
set <ll> b;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> n >> q;
for(int i = 1 ; i <= n ; ++i){
	cin >> a[i];
	c[i] = a[i];
}
if(a[1] != 1){
	s.insert((nes){1, a[1] - 1});
}
for(int i = 2 ; i <= n ; ++i){
	if(a[i] != a[i - 1] + 1){
		s.insert((nes){a[i - 1] + 1, a[i] - 1});
	}
}
if(a[n] != m){
	s.insert((nes){a[n] + 1, m});
}
for(int i = n + 1 ; i <= min(m, 300000LL) ; ++i){
	nes o = *s.begin();
	s.erase(s.begin());
	ll mid = (o.l + o.r) / 2;
	c[i] = mid;
	if(mid > o.l){
		s.insert((nes){o.l, mid - 1});
	}
	if(o.r > mid){
		s.insert((nes){mid + 1, o.r});
	}
}
for(int i = 0 ; i < q ; ++i){
	ll x;
	cin >> x;
	cout << c[x] << endl;
}

return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...