Submission #12983

#TimeUsernameProblemLanguageResultExecution timeMemory
12983tncks0121케이크 (JOI13_cake)C++14
0 / 100
0 ms12816 KiB
#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) { if(s == e) return 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() { 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(N % 2 == 1) ans[i] += A[1]; printf("%lld\n", ans[i]); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...