oj.uz

답안 #346733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
346733 2021-01-10T20:48:35 Z guka415 OGLEDALA (COI15_ogledala) C++14
41 / 100
 4000 ms 305300 KB 
#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define ff first
#define ss second

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <unordered_map>

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

const int sz = 1e5 + 5;
ll m, n, q;
ll a[sz], b[sz];
int segsSize, lensSize;
vector<pll> segs;
vector<pair<pll, ll>> lensAll; //len, -idx, amt
vector<pll> lens[sz];

void input() {
	cin >> m >> n >> q;
	foru(i, 0, n) {
		cin >> a[i]; a[i]--;
	}
	foru(i, 0, q) {
		cin >> b[i]; b[i]--;
	}
	if (a[0] != 0)segs.pb({ a[0],-1 });
	foru(i, 0, n - 1) {
		if (a[i + 1] - a[i] != 1)segs.pb({ a[i + 1] - a[i] - 1,i });
	}
	if (a[n - 1] != m - 1)segs.pb({ m - 1 - a[n - 1],n - 1 });
	segsSize = segs.size();
}

void interpretSegs() {
	map<ll, ll, greater<ll>> mem;
	foru(idx, 0, segsSize) {
		mem[segs[idx].ff] = 1;
		while (!mem.empty()) {
			pll x = *mem.begin(); mem.erase(x.first);
			lens[idx].pb(x);
			lensAll.pb({ {x.ff, -idx},x.ss });
			ll amt = x.ff;
			if (amt & 1) {
				if (amt != 1)mem[amt >> 1] += (x.ss * 2);
			}
			else {
				mem[amt >> 1] += x.ss;
				if (amt != 2)mem[(amt >> 1) - 1] += x.ss;
			}
		}
	}
}

ll countSegAmount(ll initialLen, ll val) {
	if (initialLen <= val)return (initialLen == val);
	unordered_map<ll, ll> mem, mem2;
	mem[initialLen] = 1;
	ll ret = 0;
	while (!mem.empty()) {
		for (pll x : mem) {
			if (x.ff == val)ret += x.ss;
			else if (x.ff > val) {
				mem2[x.ff >> 1] += x.ss;
				mem2[(x.ff - 1) >> 1] += x.ss;
			}
		}
		mem = mem2;
		mem2.clear();
	}
	return ret;
}

ll findIndex(ll serialNum, ll val, ll lseg, ll rseg) {
	ll len = rseg - lseg + 1, mid = (lseg + rseg) / 2;
	if (len == val)return mid;
	ll cntLeft = countSegAmount((len - 1) / 2, val);
	if (cntLeft >= serialNum) return findIndex(serialNum, val, lseg, mid - 1);
	else return findIndex(serialNum - cntLeft, val, mid + 1, rseg);
}

pll findLR(int id) {
	int aid = segs[id].ss;
	if (aid == -1)return { 0,a[0] - 1 };
	else if (aid == n - 1)return { a[aid] + 1,m - 1 };
	else return { a[aid] + 1,a[aid + 1] - 1 };
}

int main() {
	fast;
	input();
	interpretSegs();
	sort(lensAll.begin(), lensAll.end(), greater<pair<pll, ll>>());
	lensSize = lensAll.size();
	int qid = 0, lenid = 0;
	ll crid = n;
	while (qid < q) {
		if (b[qid] < n)cout << a[b[qid++]] + 1 << '\n';
		else {
			while (crid <= b[qid] && lenid < lensSize) {
				if (crid + lensAll[lenid].ss <= b[qid]) crid += lensAll[lenid++].ss;
				else {
					pll fs = findLR(-lensAll[lenid].ff.ss);
					cout << findIndex(b[qid++] - crid + 1, lensAll[lenid].ff.ff, fs.ff, fs.ss) + 1 << '\n';
					break;
				}
			}
		}
	}
	return 0;
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 78 ms 6568 KB Output is correct
4 Correct 52 ms 6560 KB Output is correct
5 Correct 75 ms 16096 KB Output is correct
6 Correct 73 ms 16372 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 3180 KB Output is correct
2 Correct 51 ms 3180 KB Output is correct
3 Correct 1264 ms 292116 KB Output is correct
4 Correct 1272 ms 289684 KB Output is correct
5 Correct 1400 ms 281876 KB Output is correct
6 Correct 1422 ms 280084 KB Output is correct

Subtask #3
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2746 ms 150264 KB Output is correct
2 Correct 2653 ms 146424 KB Output is correct
3 Execution timed out 4080 ms 305300 KB Time limit exceeded
4 Halted 0 ms 0 KB -