oj.uz

Submission #27477

# Submission time Handle Problem Language Result Execution time Memory
27477 2017-07-13T06:23:03 Z 김동현(#1155) OGLEDALA (COI15_ogledala) C++14
41 / 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];

priority_queue<pll> pq; 

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 = 1; i <= n + 1; i++){
		pq.push({a[i] - a[i - 1] - 1, -(a[i - 1] + 1)});
	}
	for(int i = 1, c; q--; ){
		scanf("%d", &c);
		for(; i < c; i++){
			if(i <= n) continue;
			ll l, x; tie(l, x) = pq.top(); x = -x;
			if((l - 1) / 2 > 0) pq.push({(l - 1) / 2, -x});
			if(l / 2 > 0) pq.push({l / 2, -(x + (l + 1) / 2)});
			pq.pop();
		}
		if(i <= n){
			printf("%lld\n", a[i]);
			continue;
		}
		ll l, x; tie(l, x) = pq.top(); x = -x;
		printf("%lld\n", x + (l - 1) / 2);
	}
}

Compilation message

ogledala.cpp: In function 'int main()':
ogledala.cpp:12: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:13: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:19:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
                  ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2800 KB Output is correct
2 Correct 0 ms 2800 KB Output is correct
3 Correct 46 ms 4420 KB Output is correct
4 Correct 39 ms 4420 KB Output is correct
5 Correct 99 ms 9028 KB Output is correct
6 Correct 103 ms 9028 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15176 KB Output is correct
2 Correct 53 ms 15180 KB Output is correct
3 Correct 103 ms 15172 KB Output is correct
4 Correct 86 ms 15172 KB Output is correct
5 Correct 109 ms 15172 KB Output is correct
6 Correct 113 ms 15172 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 524288 KB Execution timed out
2 Halted 0 ms 0 KB -