Submission #846350

#	Time	Username	Problem	Language	Result	Execution time	Memory
846350		vjudge1	OGLEDALA (COI15_ogledala)	C++17	19 / 100	57 ms	8960 KiB

ogledala

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 3e5 + 5;

vector<int> A;
int main() {
	fast
	int M, N, Q;
	cin >> M >> N >> Q;

	A = vector<int>(N+2);
	for (int i = 1; i <= N; i++)
		cin >> A[i];
	A[0] = 0;
	A[N+1] = M+1; 
	priority_queue<pair<int, pair<int,int>>> pq;
	for (int i = 1; i <= N+1; i++)
		pq.push({A[i]-A[i-1]-1, {-A[i-1]-1, -A[i]+1}});

	int now = N;
	int now_ans = A[N];
	for (int i = 1; i <= Q; i++) {
		int k;
		cin >> k;
		if (k <= N)
			cout << A[k] << "\n";
		else {
			while (N < k) {
				pair<int,pair<int,int>> p = pq.top();
				pq.pop();
				pair<int,pair<int,int>> q = {p.f, {-p.s.f, -p.s.s}};

				now_ans = (q.s.f + q.s.s) / 2;
				pq.push({now_ans-q.s.f, {-(q.s.f), -(now_ans - 1)}});
				pq.push({q.s.s - now_ans, {-(now_ans+1), -(q.s.s)}});
				N++;
			}
			cout << now_ans << "\n"; 
		}
	}
}

Compilation message (stderr)

ogledala.cpp: In function 'int main()':
ogledala.cpp:27:6: warning: unused variable 'now' [-Wunused-variable]
   27 |  int now = N;
      |      ^~~

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