oj.uz

Submission #387270

# Submission time Handle Problem Language Result Execution time Memory
387270 2021-04-08T08:20:11 Z sinamhdv OGLEDALA (COI15_ogledala) C++11
41 / 100
 201 ms 44268 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 100100
#define MAXB 300100

ll m;
int n, q;
ll a[MAXB];

int32_t main(void)
{
	fast_io;
	cin >> m >> n >> q;

	FOR(i, 1, n + 1)
		cin >> a[i];
	
	set<pair<ll, pll>> s;

	if (a[1] > 1)
		s.insert({a[1] - 1, {-1, a[1] - 1}});
	if (a[n] < m)
		s.insert({m - a[n], {-(a[n] + 1), m}});

	FOR(i, 2, n + 1)
	{
		if (a[i] == a[i - 1] + 1)
			continue;
		s.insert({a[i] - a[i - 1] - 1, {-(a[i - 1] + 1), a[i] - 1}});
	}

	FOR(i, n + 1, min((ll)MAXB, m + 1))
	{
		pll p = s.rbegin() -> sc;
		auto it = s.end();
		it--;
		s.erase(it);

		p.fr = -p.fr;

		a[i] = (p.fr + p.sc) / 2;
		
		if (a[i] != p.fr)
			s.insert({a[i] - p.fr, {-p.fr, a[i] - 1}});
		
		if (a[i] != p.sc)
			s.insert({p.sc - a[i], {-(a[i] + 1), p.sc}});
	}

	while (q--)
	{
		int b;
		cin >> b;
		cout << a[b] << endl;
	}

	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 34 ms 4204 KB Output is correct
4 Correct 35 ms 4332 KB Output is correct
5 Correct 77 ms 11400 KB Output is correct
6 Correct 85 ms 12012 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 21612 KB Output is correct
2 Correct 119 ms 21612 KB Output is correct
3 Correct 184 ms 24712 KB Output is correct
4 Correct 201 ms 24812 KB Output is correct
5 Correct 182 ms 25068 KB Output is correct
6 Correct 184 ms 25196 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 191 ms 44268 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -