This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int N_ = 300500;
const int lgN_ = 19;
const int LEAF = 1 << lgN_;
int N, A[N_], S = 1, A_tmp[N_];
int tree[2<<lgN_];
int better_A (int x, int y) {
return A[x] < A[y] ? x : y;
}
int get_min_pos (int x, int y) {
int ret = x;
x += LEAF; y += LEAF;
while(x <= y) {
if((x & 1) == 1) ret = better_A(ret, tree[x]);
if((y & 1) == 0) ret = better_A(ret, tree[y]);
x = (x + 1) >> 1;
y = (y - 1) >> 1;
}
return ret;
}
ll sum2[N_];
ll ans[N_];
void add_ans (int l, int r, ll v) {
ans[l] += v;
ans[r+1] -= v;
}
ll sk_sum (int s, int e, int first) { // [s..e]를 번갈아 가며 먹으면 석환이가 얼마나 먹는가?
first %= 2;
if(first == 0) return sk_sum(s + ((s <= e) ? +1 : -1), e, 1);
if(s <= e) return sum2[e - (e - s) % 2] - sum2[max(0, s-2)];
else return sum2[s] - sum2[max(0, e + (s - e) % 2 - 2)];
}
void solve(int l, int r) {
if(l > r) {
return;
}
if(l == r) {
add_ans(l, r, A[l]);
return;
}
if(r == l + 1) {
add_ans(l, l, A[l]);
add_ans(r, r, A[r]);
return;
}
int m = get_min_pos (l, r);
solve(l, m-1);
add_ans(m+1, r, sk_sum(m, l, (r - m + 1) % 2));
solve(m+1, r);
add_ans(l, m-1, sk_sum(m, r, (m - l + 1) % 2));
{
add_ans(m, m, A[m]);
int x = l, y = r;
while(x <= m && m <= y) {
int nx = get_min_pos(x, m-1);
int ny = get_min_pos(m+1, y);
if(A[nx] <= A[ny]) { // nx 선택 -> 이후 모두 번갈아가면서 선택함
add_ans(m, m, sk_sum(nx, x, (y - nx + 1) % 2));
x = nx+1;
}else {
add_ans(m, m, sk_sum(ny, y, (ny - x + 1) % 2));
y = ny-1;
}
if(x == m) ++x;
if(y == m) --y;
}
if(y < m) add_ans(m, m, sk_sum(y, x, 0));
else add_ans(m, m, sk_sum(x, y, 0));
}
}
int main() {
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d", &N);
for(int i = 1; i <= N; i++) {
scanf("%d", A_tmp + i);
if(A_tmp[i] < A_tmp[S]) {
S = i;
}
}
A[0] = (int)2e9;
for(int i = 1, j = S; i <= N; i++) {
A[i] = A_tmp[j++];
tree[i + LEAF] = i;
if(j > N) j = 1;
}
for(int i = LEAF-1; i >= 1; i--) tree[i] = better_A(tree[i+i], tree[i+i+1]);
sum2[0] = 0;
sum2[1] = A[1];
sum2[2] = A[2];
for(int i = 3; i <= N+5; i++) {
sum2[i] = sum2[i-2] + A[i];
}
solve(2, N);
for(int i = 1; i <= N; i++) ans[i] += ans[i-1];
{
int l = 2, r = N;
for(int t = 0; l <= r; t = !t) {
int s = 0;
if(A[l] < A[r]) s = A[l++]; else s = A[r--];
if(t) ans[1] += s;
}
}
for(int i = (N-S+1)%N+1, j = 1; j <= N; i = i%N+1, j++) {
if(i > 1 && N % 2 == 1) ans[i] += A[1];
printf("%lld\n", ans[i]);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |