Submission #17549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
17549	2015-12-26T15:44:58 Z	gs14004	케이크 (JOI13_cake)	C++14	100 / 100	196 ms	32456 KB

cake

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <complex>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
typedef complex<double> pnt;

int a[300005], n;
lint ret[300005], sum[2][300005];
int rotp;

struct rmq{
	pi tree[1050000];
	int lim;
	void init(int n, int *a){
		for(lim = 1; lim <= n; lim <<= 1);
		fill(tree, tree + 1050000, pi(1e9, 1e9));
		for(int i=0; i<n; i++){
			tree[i+lim] = pi(a[i], i);
		}
		for(int i=lim-1; i; i--){
			tree[i] = min(tree[2*i], tree[2*i+1]);
		}
	}
	pi query(int s, int e){
		pi ret(1e9, 1e9);
		s += lim;
		e += lim;
		while(s < e){
			if(s%2 == 1) ret = min(ret, tree[s++]);
			if(e%2 == 0) ret = min(ret, tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = min(ret, tree[s]);
		return ret;
	}
}rmq;

lint expand(int x, int s, int e){
	int ps = s, pe = e;
	lint ret = a[x];
	while(ps < x || x < pe){
		pi t1 = rmq.query(ps, x-1);
		pi t2 = rmq.query(x+1, pe);
		if(t1.first < t2.first){
			ret += sum[pe%2][t1.second] - sum[pe%2][ps-1];
			ps = t1.second + 1;
		}
		else{
			ret += sum[ps%2][pe] - sum[ps%2][t2.second-1];
			pe = t2.second - 1;
		}
	}
	return ret;
}

void solve(int s, int e, lint alt0, lint alt1){
	if(s > e) return;
	int p = rmq.query(s, e).second;
	ret[p] = expand(p, s, e) + alt0;
	lint nalt0 = sum[s%2][e] - sum[s%2][p-1];
	lint nalt1 = sum[(s+1)%2][e] - sum[(s+1)%2][p-1];
	solve(s, p-1, nalt0 + alt0, nalt1 + alt1);
	nalt0 = sum[e%2][p] - sum[e%2][s-1];
	nalt1 = sum[(e+1)%2][p] - sum[(e+1)%2][s-1];
	solve(p+1, e, nalt0 + alt0, nalt1 + alt1);
} 

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
	}
	rotp = min_element(a, a+n) - a;
	rotate(a, a + rotp, a+n);
	for(int i=0; i<n; i++){
		if(i){
			sum[0][i] = sum[0][i-1];
			sum[1][i] = sum[1][i-1];
		}
		sum[i%2][i] += a[i];
	}
	rmq.init(n, a);
	ret[0] = a[0];
	int s = 1, e = n-1;
	for(int i=0; i<n-1; i++){
		if(a[s] < a[e]){
			if(i%2 == 1) ret[0] += a[e];
			e--;
		}
		else{
			if(i%2 == 1) ret[0] += a[s];
			s++;
		}
	}
	if(n%2 == 1) solve(1, n-1, a[0], 0);
	else solve(1, n-1, 0, a[0]);
	rotate(ret, ret + n - rotp, ret + n);
	for(int i=0; i<n; i++){
		printf("%lld\n",ret[i]);
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	18128 KB	Output is correct
2	Correct	0 ms	18128 KB	Output is correct
3	Correct	6 ms	18128 KB	Output is correct
4	Correct	3 ms	18128 KB	Output is correct
5	Correct	7 ms	18276 KB	Output is correct
6	Correct	7 ms	18128 KB	Output is correct
7	Correct	0 ms	18128 KB	Output is correct
8	Correct	7 ms	18128 KB	Output is correct
9	Correct	0 ms	18128 KB	Output is correct
10	Correct	4 ms	18128 KB	Output is correct
11	Correct	4 ms	18128 KB	Output is correct

Subtask #2

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	18224 KB	Output is correct
2	Correct	47 ms	18156 KB	Output is correct
3	Correct	78 ms	18284 KB	Output is correct
4	Correct	154 ms	18128 KB	Output is correct
5	Correct	116 ms	18128 KB	Output is correct
6	Correct	179 ms	18128 KB	Output is correct
7	Correct	190 ms	19824 KB	Output is correct
8	Correct	188 ms	18128 KB	Output is correct
9	Correct	128 ms	18128 KB	Output is correct
10	Correct	180 ms	18128 KB	Output is correct
11	Correct	158 ms	19096 KB	Output is correct
12	Correct	157 ms	20188 KB	Output is correct
13	Correct	193 ms	32456 KB	Output is correct
14	Correct	176 ms	18128 KB	Output is correct
15	Correct	196 ms	19988 KB	Output is correct