Submission #12986

#	Time	Username	Problem	Language	Result	Execution time	Memory
12986		tncks0121	케이크 (JOI13_cake)	C++14	100 / 100	164 ms	40812 KiB

cake

#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_)+10];
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));
    
    {
        ll ans_m = 0;//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 선택 -> 이후 모두 번갈아가면서 선택함
                ans_m += sk_sum(nx, x, (y - nx + 1) % 2);
                x = nx+1;
            }else {
                ans_m += sk_sum(ny, y, (ny - x + 1) % 2);
                y = ny-1;
            }
        }
        
        ans_m += (y <= m) ? sk_sum(m, x, 1) : sk_sum(m, y, 1);
        add_ans(m, m, ans_m);
    }
}

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]; j = j % N + 1;
        tree[i + LEAF] = i;
    }
    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 ", ans[i]);
    }
    
    
    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90