Submission #90722

#	Time	Username	Problem	Language	Result	Execution time	Memory
90722		jasony123123	OGLEDALA (COI15_ogledala)	C++11	100 / 100	2255 ms	213964 KiB

ogledala

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/****************************************************************/

struct Seg {
	ll len, midx, cnt;
	Seg(ll a, ll b, ll c) {
		len = a, midx = b, cnt = c;
	}
	bool operator<(const Seg &other) const {
		return mp(-len, midx) < mp(-other.len, other.midx);
	}
};

const int MAXN = 100100, MAXQ = 100100;
ll M, N, Q;
ll iniLpos[MAXN];
ll qLidx[MAXQ];
v<Seg> allsegs;
v<ll> queryLidx;
v<pll> mainseg; // all of the mainsegments

void precomputeSegs() {
	pll temp = { 1, iniLpos[0] - 1 };
	if (temp.first <= temp.second)
		mainseg.push_back(temp);
	FOR(i, 0, N - 1) {
		pll temp = { iniLpos[i] + 1, iniLpos[i + 1] - 1 };
		if (temp.first <= temp.second)
			mainseg.push_back(temp);
	}
	temp = { iniLpos[N - 1] + 1, M };
	if (temp.first <= temp.second)
		mainseg.push_back(temp);

	FOR(i,0,mainseg.size() ){
		pll seg = mainseg[i];
		ll len = seg.second - seg.first + 1;
		priority_queue<ll> avalen;
		map<ll, ll> cnt = { { len, 1 } }; // cnt of seg[len]
		avalen.push(len);
		while (!avalen.empty()) {
			len = avalen.top();
			avalen.pop();
			ll num = cnt[len];
			pll newlen = { len / 2LL, (len - 1LL) / 2LL };

			if (cnt.find(newlen.first) == cnt.end() && newlen.first > 1)
				avalen.push(newlen.first);
			if (newlen.first>0)
				cnt[newlen.first] += num;

			if (cnt.find(newlen.second) == cnt.end() && newlen.second > 1)
				avalen.push(newlen.second);
			if (newlen.second>0)
				cnt[newlen.second] += num;
		}
		for (auto &a : cnt)
			allsegs.push_back(Seg(a.first, i, a.second));
	}
	sort(all(allsegs));
}


ll dfs(ll curlen, ll tarlen, map<ll, ll> &dp) {
	if (curlen < tarlen) return 0;
	if (dp.find(curlen) != dp.end()) return dp[curlen];
	return dp[curlen] = dfs(curlen / 2LL, tarlen, dp) + dfs((curlen - 1LL) / 2LL, tarlen, dp);
}

ll process(ll targetLen, ll targetKth, int mainIdx) {
//	cout << " target len = " << targetLen << " target Kth " << targetKth << "  in interval: " << mainseg[mainIdx].first << " - " << mainseg[mainIdx].second << "\n";
	map<ll, ll> cntdp = { {targetLen, 1} };
	dfs(mainseg[mainIdx].second - mainseg[mainIdx].first + 1LL, targetLen, cntdp);
/*	for (auto x : cntdp) {
		cout << x.first << " num targ len produced: " << x.second << "\n";
	}*/

	ll l = mainseg[mainIdx].first, r = mainseg[mainIdx].second;
	ll mid = (l + r) / 2, len = r - l + 1;

	while (len != targetLen) {
		ll lftCnt = cntdp[mid - 1LL - l + 1LL];
		if (lftCnt >= targetKth) {
			r = mid - 1;
		}
		else {
			l = mid + 1;
			targetKth -= lftCnt;
		}
		mid = (l + r) / 2, len = r - l + 1;
	}
	return mid;
}

void find() {
/*	for (auto x : allsegs) {
		cout << x.cnt << " " << x.len << " " << x.midx << "\n";
	}*/

	ll seen = N;
	for (int i = 0, j = 0; i < allsegs.size() && j < queryLidx.size();) {
		if (seen + allsegs[i].cnt < queryLidx[j]) {
			seen += allsegs[i].cnt;
			i++;
		}
		else {
			cout << process(allsegs[i].len, queryLidx[j] - seen, allsegs[i].midx) << "\n";
			j++;
		}
	}
}

int main() {
	io();
	cin >> M >> N >> Q;
	FOR(i, 0, N) cin >> iniLpos[i];
	precomputeSegs();
	FOR(i, 0, Q) {
		ll bLidx;
		cin >> bLidx;
		if (bLidx <= N)
			cout << iniLpos[bLidx - 1] << "\n";
		else
			queryLidx.push_back(bLidx);
	}
	find();
	return 0;
}

Compilation message (stderr)

ogledala.cpp: In function 'void find()':
ogledala.cpp:141:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, j = 0; i < allsegs.size() && j < queryLidx.size();) {
                         ~~^~~~~~~~~~~~~~~~
ogledala.cpp:141:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, j = 0; i < allsegs.size() && j < queryLidx.size();) {
                                               ~~^~~~~~~~~~~~~~~~~~

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