답안 #27513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27513 2017-07-13T08:26:16 Z 김동현(#1155) OGLEDALA (COI15_ogledala) C++14
19 / 100
4000 ms 524288 KB
#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];
map<ll, ll> tmp;
map<ll, vector<pll>> pmp;
map<ll, map<ll, ll>> dp;

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;

void f(ll x){
	if(!x || dp.find(x) != dp.end()) return;
	if(x == 1){
		dp[1][1]++;
		return;
	}
	if((x - 1) / 2){
		f((x - 1) / 2);
		for(auto &i : dp[(x - 1) / 2]) dp[x][i.first] += i.second;
	}
	if(x / 2){
		f(x / 2);
		for(auto &i : dp[x / 2]) dp[x][i.first] += i.second;
	}
	dp[x][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 = val((x - 1) / 2, t);
	if(v == c - 1 && x == 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;
		f(l[i]);
		for(auto &j : dp[l[i]]){
			tmp[j.first] += j.second;
			pmp[j.first].push_back({i, j.second});
		}
	}
	for(auto &i : pmp){
		tr[i.first] = new Seg(i.second);
	}
	auto t = tmp.end(); t--;
	ll cs = 0;
	for(ll c; q--; ){
		scanf("%lld", &c);
		if(c <= n){
			printf("%lld\n", a[c]);
			continue;
		}
		c -= n;
		while(cs + t->second < c){
			cs += t->second;
			t--;
		}
		c -= cs;
		ll u, d; tie(u, d) = tr[t->first]->get(c);
		printf("%lld\n", g(l[u], s[u], t->first, d));
	}
}

Compilation message

ogledala.cpp: In constructor 'Seg::Seg(const std::vector<std::pair<long long int, long long int> >&)':
ogledala.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(sz = 1; sz < v.size(); sz *= 2);
                  ^
ogledala.cpp:19: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:69: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:70: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:87:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &c);
                    ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5156 KB Output is correct
2 Correct 0 ms 5156 KB Output is correct
3 Correct 33 ms 7236 KB Output is correct
4 Correct 26 ms 7340 KB Output is correct
5 Correct 69 ms 13652 KB Output is correct
6 Correct 53 ms 14484 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 11228 KB Output is correct
2 Correct 49 ms 11756 KB Output is correct
3 Memory limit exceeded 2816 ms 524288 KB Memory limit exceeded
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4000 ms 460212 KB Execution timed out
2 Halted 0 ms 0 KB -