Submission #24926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24926	2017-06-17T08:15:00 Z	kdh9949	케이크 (JOI13_cake)	C++14	0 / 100	1500 ms	47580 KB

cake

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf = 2e9;
int n, mn = inf, mi;
int a[900010], pw[4444444];
ll cans, sum[2][900010], ans[300010];

const int sz = 1048576;
struct Seg{
	int dat[2 * sz];
	void ini(){ fill(dat, dat + 2 * sz, inf); }
	void upd(int x, int v){
		x += sz - 1; dat[x] = v;
		for(x /= 2; x; x /= 2) dat[x] = min(dat[2 * x], dat[2 * x + 1]);
	}
	int mni(int h, int l){
		l += sz - 1;
		while(l > 1 && !pw[l + 1]){
			if(dat[l] < h) break;
			l = (l + 1) / 2;
		}
		while(l < sz){
			if(dat[2 * l] < h) l = 2 * l;
			else l = 2 * l + 1;
		}
		return l - sz + 1;
	}
	int mxi(int h, int r){
		r += sz - 1;
		while(r > 1 && !pw[r]){
			if(dat[r] < h) break;
			r = (r - 1) / 2;
		}
		while(r < sz){
			if(dat[2 * r + 1] < h) r = 2 * r + 1;
			else r = 2 * r;
		}
		return r - sz + 1;
	}
} S;

void f(int s, int e, int x){
	if(e - s - 1 == n - 1){ ans[s > n ? s - n : s] = cans + a[s]; return; }
	int l = max(e - n, S.mxi(a[e], s) - 1);
	int tb = !(x ^ (s % 2));
	ll ts = sum[tb][s] - sum[tb][l];
	cans += ts;
	f(l, e, x ^ ((s - l) % 2));
	cans -= ts;
	int r = min(s + n, S.mni(a[s], e) + 1);
	tb = !(x ^ (e % 2));
	ts = sum[tb][r - 1] - sum[tb][e - 1];
	cans += ts;
	f(s, r, x ^ ((r - e) % 2));
	cans -= ts;
}

void g(int s, int e, int x){
	if(e - s - 1 == n) return;
	if(x){
		if(a[s] > a[e]){
			ans[mi] += a[s];
			g(s - 1, e, 0);	
		}
		else{
			ans[mi] += a[e];
			g(s, e + 1, 0);
		}
	}
	else{
		if(a[s] > a[e]) g(s - 1, e, 1);
		else g(s, e + 1, 1);
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i <= 21; i++) pw[1 << i] = 1;
	for(int i = 1; i <= n; i++){
		scanf("%d", a + i);
		a[n + i] = a[2 * n + i] = a[i];
		if(a[i] < mn){
			mn = a[i];
			mi = i;
		}
	}
	S.ini();
	for(int i = 1; i <= 3 * n; i++){
		sum[i % 2][i] = sum[i % 2][i - 1] + a[i];
		sum[!(i % 2)][i] = sum[!(i % 2)][i - 1];
		S.upd(i, a[i]);
	}
	ans[mi] = mn;
	if(n % 2) cans = mn;
	f(n + mi - 1, n + mi + 1, !(n % 2));
	g(n + mi - 1, n + mi + 1, 0);
	for(int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:79:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
cake.cpp:82:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
                     ^

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1500 ms	47580 KB	Execution timed out
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1500 ms	47496 KB	Execution timed out
2	Halted	0 ms	0 KB	-