oj.uz

Submission #114640

# Submission time Handle Problem Language Result Execution time Memory
114640 2019-06-02T06:10:15 Z maruii Candies (JOI18_candies) C++14
0 / 100
 5000 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
#define ff first
#define ss second

int L[200005], R[200005];
ll A[200005], ans;
bool used[200005];
priority_queue<pli> pq;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i], pq.emplace(A[i], i);
	iota(L + 1, L + N + 2, 0);
	iota(R, R + N + 1, 1);
	R[N+1] = N+1;
	A[0] = A[N+1] = -1e18;
	for (int i = 0; i < (N + 1 >> 1); ++i) {
		while (used[pq.top().ss]) pq.pop();
		int x = pq.top().ss; pq.pop();
		used[L[x]] = used[R[x]] = 1;
		ans += A[x];
		A[x] = A[L[x]] + A[R[x]] - A[x];
		L[x] = L[L[x]];
		R[L[x]] = x;
		R[x] = R[R[x]];
		L[R[x]] = x;
		cout << ans << '\n';
	}
	return 0;
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:21:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  for (int i = 0; i < (N + 1 >> 1); ++i) {
                       ~~^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5055 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5055 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -