답안 #12986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
12986	2015-01-23T03:22:41 Z	tncks0121	케이크 (JOI13_cake)	C++14	100 / 100	164 ms	40812 KB

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	12816 KB	Output is correct
2	Correct	4 ms	13156 KB	Output is correct
3	Correct	0 ms	12816 KB	Output is correct
4	Correct	4 ms	12816 KB	Output is correct
5	Correct	0 ms	12928 KB	Output is correct
6	Correct	0 ms	12816 KB	Output is correct
7	Correct	4 ms	12816 KB	Output is correct
8	Correct	0 ms	12816 KB	Output is correct
9	Correct	0 ms	12816 KB	Output is correct
10	Correct	0 ms	12816 KB	Output is correct
11	Correct	0 ms	12816 KB	Output is correct

Subtask #2

90.0 / 90.0

#	결과	실행 시간	메모리	Grader output
1	Correct	52 ms	12976 KB	Output is correct
2	Correct	40 ms	12932 KB	Output is correct
3	Correct	48 ms	13144 KB	Output is correct
4	Correct	104 ms	12816 KB	Output is correct
5	Correct	116 ms	12816 KB	Output is correct
6	Correct	148 ms	12816 KB	Output is correct
7	Correct	148 ms	22064 KB	Output is correct
8	Correct	152 ms	12888 KB	Output is correct
9	Correct	144 ms	12816 KB	Output is correct
10	Correct	148 ms	26752 KB	Output is correct
11	Correct	136 ms	15140 KB	Output is correct
12	Correct	156 ms	18312 KB	Output is correct
13	Correct	160 ms	25084 KB	Output is correct
14	Correct	164 ms	40812 KB	Output is correct
15	Correct	148 ms	16064 KB	Output is correct