Submission #27496

#	Time	Username	Problem	Language	Result	Execution time	Memory
27496		khsoo01	OGLEDALA (COI15_ogledala)	C++11	41 / 100	4000 ms	128260 KiB

ogledala

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

ll l, n, m, a[N], qry[N], cur[N];
vector<ll> dt[N], v[N];

priority_queue<pll> pq;

void add (vector<ll> &V, ll A) {
	if(A <= 0) return;
	for(auto &T : V) if(T == A) return;
	V.push_back(A);
}

ll geti (vector<ll> &V, ll I, ll P) {
	for(ll i=max(0ll, I-4);i<I;i++) if(V[i] == P) return i;
	return -1;
}

void kth (ll I, ll C, ll O, ll S, ll E, ll K) {
	if(C == O) {printf("%lld\n",(S+E)/2); return;}
	ll L = E-S+1, I1 = geti(v[I], C, (L-1)/2), I2 = geti(v[I], C, L/2);
	if(I1>=O && dt[I][I1] >= K) kth(I, I1, O, S, (S+E)/2-1, K);
	else kth(I, I2, O, (S+E)/2+1, E, K-(I1>=O?dt[I][I1]:0));
}

void calc (vector<ll> &D, vector<ll> &V, ll O) {
	D.clear();
	for(ll i=0;i<V.size();i++) {
		D.push_back(0);
		if(i == O) D[i] = 1;
		else if(i > O) {
			ll I1 = geti(V, i, (V[i]-1)/2), I2 = geti(V, i, V[i]/2);
			if(I1 != -1) D[i] += D[I1];
			if(I2 != -1) D[i] += D[I2];
		}
	}
}

int main() {
	scanf("%lld%lld%lld",&l,&n,&m);
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
	}
	a[n+1] = l+1;
	for(ll i=1;i<=n+1;i++) {
		add(v[i], a[i]-a[i-1]-1);
		for(ll j=0;j<v[i].size();j++) {
			add(v[i], v[i][j]/2);
			add(v[i], (v[i][j]-1)/2);
		}
		reverse(v[i].begin(), v[i].end());
	}
	for(ll i=1;i<=n+1;i++) {
		cur[i] = v[i].size();
		if(--cur[i] >= 0) {
			calc(dt[i], v[i], cur[i]);
			pq.push({v[i][cur[i]], -i});
		}
	}
	ll cq = 1, dn = n;
	for(ll i=1;i<=m;i++) {
		scanf("%lld",&qry[i]);
		if(qry[i] <= n) {
			cq++;
			printf("%lld\n",a[qry[i]]);
		}
	}
	while(!pq.empty()) {
		ll C = -pq.top().second, V = dt[C][v[C].size()-1]; pq.pop();
		for(;cq <= m && qry[cq] <= dn + V; cq++) {
			kth(C, v[C].size()-1, cur[C], a[C-1]+1, a[C]-1, qry[cq]-dn);
		}
		if(cq > m) break;
		dn += V;
		if(--cur[C] >= 0) {
			calc(dt[C], v[C], cur[C]);
			pq.push({v[C][cur[C]], -C});
		}
	}
}

Compilation message (stderr)

ogledala.cpp: In function 'void calc(std::vector<long long int>&, std::vector<long long int>&, ll)':
ogledala.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<V.size();i++) {
              ^
ogledala.cpp: In function 'int main()':
ogledala.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll j=0;j<v[i].size();j++) {
               ^
ogledala.cpp:44:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&l,&n,&m);
                                ^
ogledala.cpp:46:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^
ogledala.cpp:66:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&qry[i]);
                        ^

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