oj.uz

답안 #27568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27568 2017-07-13T08:48:18 Z 김현수(#1153) OGLEDALA (COI15_ogledala) C++14
41 / 100
 4000 ms 106364 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;

ll l, a[N], qry[N];
int n, m, cur[N];

vector<ll> v[N], dt[N];

bool cmp (int A, int B) {
	if(v[A][cur[A]] != v[B][cur[B]]) return v[A][cur[A]] < v[B][cur[B]];
	return A > B;
}

priority_queue<int, vector<int>, decltype(&cmp)> pq(&cmp);

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

void add (vector<ll> &V, ll A) {
	if(A <= 0 || geti(V, V.size(), A) != -1) return;
	V.push_back(A);
}

void kth (int I, int C, int O, ll S, ll E, ll K) {
	if(C == O) {printf("%lld\n",(S+E)/2); return;}
	ll L = E-S+1;
	int I1 = geti(v[I], C, (L-1)/2), I2 = (L/2 == (L-1)/2 ? I1 : I1+1);
	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, int O) {
	for(int i=0;i<O;i++) D[i] = 0;
	D[O] = 1;
	for(int i=O+1;i<V.size();i++) {
		ll I1 = geti(V, i, (V[i]-1)/2), I2 = (V[i]/2 == (V[i]-1)/2 ? I1 : I1+1);
		D[i] = (I1 != -1 ? D[I1] : 0) + (I2 != -1 ? D[I2] : 0);
	}
}

int main() {
	scanf("%lld%d%d",&l,&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	a[n+1] = l+1;
	for(int 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(int i=1;i<=n+1;i++) {
		cur[i] = v[i].size();
		dt[i].resize(v[i].size());
		if(--cur[i] >= 0) {
			calc(dt[i], v[i], cur[i]);
			pq.push(i);
		}
	}
	int cq = 1; ll dn = n;
	for(int i=1;i<=m;i++) {
		scanf("%lld",&qry[i]);
		if(qry[i] <= n) {printf("%lld\n",a[qry[i]]); cq++;}
	}
	while(!pq.empty()) {
		int C = pq.top(); ll 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(C);
		}
	}
}

Compilation message

ogledala.cpp: In function 'void calc(std::vector<long long int>&, std::vector<long long int>&, int)':
ogledala.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=O+1;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:46:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%d%d",&l,&n,&m);
                            ^
ogledala.cpp:47:43: 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:67: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.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 8664 KB Output is correct
2 Correct 0 ms 8664 KB Output is correct
3 Correct 39 ms 9604 KB Output is correct
4 Correct 36 ms 9720 KB Output is correct
5 Correct 186 ms 14072 KB Output is correct
6 Correct 216 ms 14988 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 569 ms 100000 KB Output is correct
4 Correct 636 ms 101200 KB Output is correct
5 Correct 629 ms 105276 KB Output is correct
6 Correct 589 ms 106364 KB Output is correct

Subtask #3
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4000 ms 63884 KB Execution timed out
2 Halted 0 ms 0 KB -