Submission #12977

#	Time	Username	Problem	Language	Result	Execution time	Memory
12977		ainta	케이크 (JOI13_cake)	C++98	100 / 100	256 ms	27528 KiB

cake

#include<stdio.h>
#include<algorithm>
using namespace std;
#define N_ 301000
#define INF 1999999999
#define SZ 524288
int n, w[N_], TP[N_];
int p1[N_], p2[N_];
int Match[N_], Next2[N_], Prev2[N_];
long long Sum[N_][2];
long long Res[N_], SS[N_][2];
void Pro1(int b, int m, int e){
	int pv1 = m, pv2 = m + 1, c = 0, i;
	long long S1 = 0, S2 = 0;
	while (pv1 >= b || pv2 <= e){
		c++;
		if (w[pv1] > w[pv2]){
			SS[pv1][0] = S1, SS[pv1][1] = S2;
			if (c & 1)S1 += w[pv1];
			else S2 += w[pv1];
			Match[pv1] = pv2 - 1;
			pv1--;
		}
		else{
			SS[pv2][0] = S1, SS[pv2][1] = S2;
			if (c & 1)S1 += w[pv2];
			else S2 += w[pv2];
			Match[pv2] = pv1 + 1;
			pv2++;
		}
	}
	Match[b - 1] = e, Match[e + 1] = b;
	for (i = b; i <= e; i++){
		SS[i][0] = S1 - SS[i][0];
		SS[i][1] = S2 - SS[i][1];
		if ((Match[i] + i) % 2 == 1)swap(SS[i][0], SS[i][1]);
	}
}
long long Calc(int s, int l, int ck){
	if (s <= l)return Sum[l][(s & 1) ^ ck] - Sum[s - 1][(s & 1) ^ ck];
	return Sum[s][(s & 1) ^ ck] - Sum[l - 1][(s & 1) ^ ck];
}
void Add1(int a, int b, int e, int s, int l){
	Res[a] += Calc(s, l, (e - b + 1) & 1);
}
void Add2(int a, int b, int e, int x){
	Res[a] += SS[x][(e - b + 1) % 2];
}
void Do(int b, int e){
	if (e < b)return;
	if (b == e){
		Res[b] += w[b];
		return;
	}
	int m = (b + e) >> 1, i, c1 = 0, c2 = 0, M = INF, j, t;
	for (i = m; i >= b - 1; i--){
		if (M > w[i]){
			M = w[i];
			if (i != m) Do(i + 1, t);
			t = i - 1;
		}
	}
	M = INF;
	for (i = m + 1; i <= e + 1; i++){
		if (M > w[i]){
			M = w[i];
			if (i != m + 1)Do(t, i - 1);
			t = i + 1;
		}
	}
	c1 = c2 = 0; M = INF;
	for (i = m; i >= b; i--){
		if (M > w[i])M = w[i], p1[++c1] = i;
	}
	M = INF;
	for (i = m + 1; i <= e; i++){
		if (M > w[i])M = w[i], p2[++c2] = i;
	}
	p1[++c1] = b - 1, p2[++c2] = e + 1;
	Pro1(b, m, e);
	for (i = 1; i < c1; i++){
		for (j = p1[i + 1] + 1; j <= p1[i] - 1; j++){
			Add1(j, p1[i + 1] + 1, p1[i] - 1, p1[i], Match[p1[i + 1]]);
			Add2(j, p1[i + 1] + 1, Match[p1[i + 1]], p1[i + 1]);
		}
	}
	for (i = 1; i < c2; i++){
		for (j = p2[i] + 1; j <= p2[i + 1] - 1; j++){
			Add1(j, p2[i] + 1, p2[i + 1] - 1, p2[i], Match[p2[i + 1]]);
			Add2(j, Match[p2[i + 1]], p2[i + 1] - 1, p2[i + 1]);
		}
	}
	for (i = 1; i < c1; i++){
		int ed = p1[i];
		for (j = p1[i] - 1; j >= p1[i + 1]; j--){
			Add1(p1[i], j + 2, ed, j + 1, j + 1);
			if (j == p1[i + 1])t = Match[j];
			else t = Next2[j] - 1;
			if (ed < t){
				Add1(p1[i], j + 1, ed, ed + 1, t);
				ed = t;
			}
		}
		Add2(p1[i], p1[i + 1] + 1, Match[p1[i + 1]], p1[i + 1]);
	}
	for (i = 1; i < c2; i++){
		int be = p2[i];
		for (j = p2[i] + 1; j <= p2[i + 1]; j++){
			Add1(p2[i], be, j - 2, j - 1, j - 1);
			if (j == p2[i + 1])t = Match[j];
			else t = Prev2[j] + 1;
			if (be > t){
				Add1(p2[i], be, j - 1, be - 1, t);
				be = t;
			}
		}
		Add2(p2[i], Match[p2[i + 1]], p2[i + 1] - 1, p2[i + 1]);
	}
}
struct order{
	int a, num;
	bool operator<(const order &p)const{
		return a < p.a;
	}
}ord[N_];
int IT[SZ * 2 + 2];
void Add(int a){
	a += SZ;
	while (a){
		IT[a]++;
		a >>= 1;
	}
}
int Gap1(int b){
	b += SZ;
	int e = SZ + SZ - 1, r = 0;
	while (b <= e){
		if (b & 1){
			if (r + IT[b] >= 2)break;
			r += IT[b];
		}
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	if (b > e)return n + 1;
	while (b < SZ){
		if (IT[b * 2] >= 2 - r)b = b * 2;
		else{
			r += IT[b * 2];
			b = b * 2 + 1;
		}
	}
	return b - SZ;
}
int Gap2(int e){
	e += SZ;
	int b = SZ, r = 0;
	while (b <= e){
		if (!(e & 1)){
			if (r + IT[e] >= 2)break;
			r += IT[e];
		}
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	if (b > e)return 0;
	while (e < SZ){
		if (IT[e * 2 + 1] >= 2 - r)e = e * 2 + 1;
		else{
			r += IT[e * 2 + 1];
			e = e * 2;
		}
	}
	return e - SZ;
}
void PrePro(){
	int i;
	for (i = 1; i <= n; i++){
		ord[i].a = w[i], ord[i].num = i;
	}
	sort(ord + 1, ord + n + 1);
	for (i = 1; i <= n; i++){
		Next2[ord[i].num] = Gap1(ord[i].num + 1);
		Prev2[ord[i].num] = Gap2(ord[i].num - 1);
		Add(ord[i].num);
	}
}
int main(){
	int i, M, st, pv1, pv2, tp;
	scanf("%d", &n);
	for (i = 1; i <= n; i++){
		scanf("%d", &w[i]);
		if (i == 1 || M > w[i]){
			M = w[i], st = i;
		}
	}
	for (i = 1; i <= st; i++)TP[i] = w[i];
	for (i = 1; i <= n - st; i++)w[i] = w[i + st];
	for (i = n - st + 1; i <= n; i++)w[i] = TP[i - n + st];
	pv1 = 1, pv2 = n - 1;
	Res[n] = w[n];
	tp = w[n];
	M = 0;
	while (pv1 <= pv2){
		M++;
		if (w[pv1] < w[pv2]){
			if (M % 2 == 0)Res[n] += w[pv2];
			pv2--;
		}
		else{
			if (M % 2 == 0)Res[n] += w[pv1];
			pv1++;
		}
	}
	w[0] = w[n] = 0;
	n--;
	PrePro();
	for (i = 1; i <= n; i++){
		Sum[i][0] = Sum[i - 1][0], Sum[i][1] = Sum[i - 1][1];
		Sum[i][i % 2] += w[i];
	}
	Do(1, n);
	if (n % 2 == 0){
		for (i = 1; i <= n; i++)Res[i] += tp;
	}
	n++;
	for (i = n - st + 1; i <= n; i++)printf("%lld\n", Res[i]);
	for (i = 1; i <= n - st; i++)printf("%lld\n", Res[i]);
}

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