Submission #27587

#	Time	Username	Problem	Language	Result	Execution time	Memory
27587		kdh9949	OGLEDALA (COI15_ogledala)	C++14	0 / 100	4000 ms	524288 KiB

ogledala

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int n, q;
ll m, a[100010], l[200010], s[100010];
set<ll> ss;
vector<ll> cpr;
ll tmp[2000010];
map<ll, ll> dp[2000010];
vector<pll> pmp[2000010];

struct Seg{
	int sz;
	ll *p, *dat;
	Seg(const vector<pll> &v){
		for(sz = 1; sz < v.size(); sz *= 2);
		p = new ll[int(v.size())];
		dat = new ll[2 * sz];
		for(int i = 0; i < v.size(); i++){
			p[i] = v[i].first;
			dat[i + sz] = v[i].second;
		}
		fill(dat + sz + int(v.size()), dat + 2 * sz, 0);
		for(int i = sz - 1; i >= 1; i--){
			dat[i] = dat[2 * i] + dat[2 * i + 1];
		}
	}
	pll get(ll v){
		int x = 1;
		while(x < sz){
			if(dat[2 * x] < v){
				v -= dat[2 * x];
				x = 2 * x + 1;
			}
			else x = 2 * x;
		}
		return {p[x - sz], v};
	}
};
map<ll, Seg*> tr;

int wh(ll x){ return int(lower_bound(cpr.begin(), cpr.end(), x) - cpr.begin());}

void pf(ll x){
	if(!x || ss.find(x) != ss.end()) return;
	ss.insert(x);
	pf((x - 1) / 2);
	pf(x / 2);
}

void f(ll x){
	if(!x || ss.find(x) != ss.end()) return;
	ss.insert(x);
	if(x == 1){
		dp[wh(1)][1]++;
		return;
	}
	int tt = wh(x);
	if((x - 1) / 2){
		f((x - 1) / 2);
		int t = wh((x - 1) / 2);
		for(auto &i : dp[t]) dp[tt][i.first] += i.second;
	}
	if(x / 2){
		f(x / 2);
		int t = wh(x / 2);
		for(auto &i : dp[t]) dp[tt][i.first] += i.second;
	}
	dp[tt][x]++;
}

ll val(ll x, ll y){ return (dp[x].find(y) == dp[x].end()) ? 0 : dp[x][y]; }

ll g(ll x, ll s, ll t, ll c){
	ll v = ((x - 1) / 2) ? val(wh((x - 1) / 2), cpr[t]) : 0;
	if(v == c - 1 && x == cpr[t]) return s + (x - 1) / 2;
	if(v >= c) return g((x - 1) / 2, s, t, c);
	return g(x / 2, s + (x + 1) / 2, t, c - v);
}

int main(){
	scanf("%lld%d%d", &m, &n, &q);
	for(int i = 1; i <= n; i++) scanf("%lld", a + i);
	a[n + 1] = m + 1;
	for(int i = 0; i <= n; i++){
		l[i] = a[i + 1] - a[i] - 1;
		s[i] = a[i] + 1;
		pf(l[i]);
	}
	while(!ss.empty()){
		cpr.push_back(*ss.begin());
		ss.erase(ss.begin());
	}
	for(int i = 0; i <= n; i++){
		f(l[i]);
		int t = wh(l[i]);
		for(auto &j : dp[t]){
			int u = wh(j.first);
			tmp[u] += j.second;
			pmp[u].push_back({i, j.second});
		}
	}
	for(int i = 0; i <= 2000000; i++){
		if(!pmp[i].empty()) tr[i] = new Seg(pmp[i]);
		pmp[i].clear();
	}
	int t = 1999999;
	ll cs = 0;
	for(ll c; q--; ){
		scanf("%lld", &c);
		if(c <= n){
			printf("%lld\n", a[c]);
			continue;
		}
		c -= n;
		while(cs + tmp[t] < c){
			cs += tmp[t];
			t--;
		}
		c -= cs;
		ll u, d; tie(u, d) = tr[t]->get(c);
		printf("%lld\n", g(l[u], s[u], t, d));
	}
}

Compilation message (stderr)

ogledala.cpp: In constructor 'Seg::Seg(const std::vector<std::pair<long long int, long long int> >&)':
ogledala.cpp:18:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(sz = 1; sz < v.size(); sz *= 2);
                  ^
ogledala.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++){
                    ^
ogledala.cpp: In function 'int main()':
ogledala.cpp:84:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%d%d", &m, &n, &q);
                               ^
ogledala.cpp:85:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%lld", a + i);
                                                  ^
ogledala.cpp:112:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &c);
                    ^

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