oj.uz

Submission #335196

# Submission time Handle Problem Language Result Execution time Memory
335196 2020-12-11T12:21:30 Z guka415 OGLEDALA (COI15_ogledala) C++14
41 / 100
 89 ms 16600 KB 
#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (long long i = k; i < n; i++)
#define ford(i, k, n) for (long long i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <set>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

const int sz = 5e5;
ll n, m, q;
ll p[sz], qu[sz], ans[sz];

int main() {
	fast;
	cin >> m >> n >> q;
	priority_queue<pii,vector<pii>, greater<pii>> pq;
	foru(i, 0, n) {
		cin >> p[i];
		ans[i + 1] = p[i];
		if (i == 0) {
			if (p[i] != 1)pq.push({ -(p[i] - 1),1 });
		}
		if (i == n - 1) {
			if (p[i] != m)pq.push({ -(m - p[i]),p[i]+1 });
		}
		if (i!=0 && p[i]-p[i-1]>1){
			pq.push({ -(p[i] - p[i - 1] - 1),p[i - 1] + 1 });
		}
	}
	for (int i = n + 1; i <= min(m, (ll)3e5+5) && !pq.empty(); i++) {
		pii top = pq.top(); pq.pop();
		ll len = -top.first, l = top.second, place = l + (len - 1) / 2;
		ans[i] = place;
		ll llen = (len - 1) / 2, rlen = len / 2;
		if (llen != 0) {
			pq.push({ -llen,l });
		}
		if (rlen != 0)pq.push({ -rlen,l + llen + 1 });
	}
	while (q--) {
		ll rr;
		cin >> rr;
		cout << ans[rr] << '\n';
	}
	return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 30 ms 2536 KB Output is correct
4 Correct 28 ms 2536 KB Output is correct
5 Correct 63 ms 6244 KB Output is correct
6 Correct 76 ms 6244 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 10864 KB Output is correct
2 Correct 48 ms 10716 KB Output is correct
3 Correct 81 ms 13020 KB Output is correct
4 Correct 89 ms 13020 KB Output is correct
5 Correct 84 ms 13148 KB Output is correct
6 Correct 82 ms 13152 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 16600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -