Submission #24928

#	Time	Username	Problem	Language	Result	Execution time	Memory
24928		khsoo01	케이크 (JOI13_cake)	C++11	100 / 100	266 ms	58524 KiB

cake

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e18;
ll n, a[300005], ans[300005], mn = 1;
ll sum[300005], xsum[300005];

ll par[300005], s[300005], e[300005];

bool vis[300005];

vector<pll> v;

struct mintree {
	ll val[1234567], lim;
	void init () {
		for(lim=1;lim<=n;lim<<=1);
		for(ll i=1;i<=n;i++) val[i+lim] = i;
		for(ll i=lim;--i;) {
			val[i] = val[2*i+(a[val[2*i]] > a[val[2*i+1]])];
		}
	}
	ll query (ll S, ll E) {
		ll ret = S;
		S += lim; E += lim;
		while(S<=E) {
			if(S%2==1) {
				if(a[ret] > a[val[S]]) ret = val[S];
				S++;
			}
			if(E%2==0) {
				if(a[ret] > a[val[E]]) ret = val[E];
				E--;
			}
			S >>= 1; E >>= 1;
		}
		return ret;
	}
	ll lb (ll E, ll X) {
		E += lim;
		while(E&(E+1)) {
			if(a[val[E]] < X) break;
			E = (E-1)/2;
		}
		if(!(E&(E+1))) return 0;
		while(E < lim) {
			E = 2*E + (a[val[2*E+1]] < X);
		}
		return E - lim;
	}
	ll rb (ll S, ll X) {
		S += lim;
		while(S&(S-1)) {
			if(a[val[S]] < X) break;
			S = (S+1)/2;
		}
		if(!(S&(S-1))) return n+1;
		while(S < lim) {
			S = 2*S + (a[val[2*S]] >= X);
		}
		return S - lim;
	}
} mt;

struct sumtree {
	ll val[1234567], lim;
	void init () {
		for(lim=1;lim<=n;lim<<=1);
	}
	void update (ll S, ll E, ll X) {
		S += lim; E += lim;
		while(S <= E) {
			if(S%2==1) val[S++] += X;
			if(E%2==0) val[E--] += X;
			S>>=1; E>>=1;
		}
	}
	ll query (ll P) {
		ll ret = 0; P += lim;
		while(P) {
			ret += val[P];
			P >>= 1;
		}
		return ret;
	}
} st;

ll simulate () {
	ll L = 2, R = n, ret = a[1], cur = 0;
	while(L<=R) {
		if(a[L] > a[R]) {ret += cur*a[L]; L++;}
		else {ret += cur*a[R]; R--;}
		cur ^= 1;
	}
	return ret;
}

ll getsum (ll S, ll E, ll P, ll X) {
	if(S > E) return 0;
	if(P % 2 == X) return xsum[E] - xsum[S-1];
	return (sum[E] - sum[S-1]) - (xsum[E] - xsum[S-1]);
}

void solve (ll S, ll E, ll X) {
	if(S>E) return;
	ll I = mt.query(S, E);
	st.update(S, I-1, getsum(I, E, E, X));
	solve(S, I-1, X^((E-I+1)%2));
	st.update(I+1, E, getsum(S, I, S, X));
	solve(I+1, E, X^((I-S+1)%2));
}

ll Find (ll X) {
	if(par[X] == X) return X;
	return par[X] = Find(par[X]);
}

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		if(a[i] < a[mn]) mn = i;
	}
	rotate(a+1, a+mn, a+n+1);
	for(ll i=1;i<=n;i++) {
		sum[i] = sum[i-1] + a[i];
		xsum[i] = xsum[i-1] + i%2*a[i];
	}
	ans[1] = simulate();
	mt.init();
	st.init();
	st.update(2, n, n%2*a[1]);
	solve(2, n, 1-n%2);
	for(ll i=1;i<=n;i++) {
		par[i] = i;
		v.push_back({-a[i], i});
	}
	sort(v.begin(), v.end());
	for(auto &T : v) {
		ll I = T.second, A, B;
		if(I == 1) continue;
		if(!vis[I+1] && !vis[I-1]) {
			s[I] = I; e[I] = I;
			ans[I] += a[I];
		}
		else if(!vis[I+1]) {
			A = Find(I-1);
			s[I] = s[A]; e[I] = I;
			par[A] = I;
			ans[I] += getsum(s[A], I, I, 1);
		}
		else if(!vis[I-1]) {
			A = Find(I+1);
			s[I] = I; e[I] = e[A];
			par[A] = I;
			ans[I] += getsum(I, e[A], I, 1);
		}
		else {
			A = Find(I-1); B = Find(I+1);
			ans[I] += a[I];
			ll cb = 0, lst = I;
			if(e[A]-s[A] < e[B]-s[B]) {
				for(ll i=I-1;i>=s[A];i--) {
					ll N = min(mt.rb(lst+1, a[i]), e[B]+1);
					ans[I] += getsum(lst+1, N-1, lst+1, cb);
					ll cnt = max(N-lst-1, 0ll);
					cb ^= (cnt%2);
					ans[I] += cb*a[i];
					cb ^= 1;
					lst = max(lst, N-1);
				}
				ans[I] += getsum(lst+1, e[B], lst+1, cb);
			}
			else {
				for(ll i=I+1;i<=e[B];i++) {
					ll N = max(mt.lb(lst-1, a[i]), s[A]-1);
					ans[I] += getsum(N+1, lst-1, lst-1, cb);
					ll cnt = max(lst-N-1, 0ll);
					cb ^= (cnt%2);
					ans[I] += cb*a[i];
					cb ^= 1;
					lst = min(lst, N+1);
				}
				ans[I] += getsum(s[A], lst-1, lst-1, cb);
			}
			s[I] = s[A]; e[I] = e[B];
			par[A] = I; par[B] = I;
		}
		vis[I] = true;
	}
	for(ll i=1;i<=n;i++) ans[i] += st.query(i);
	rotate(ans+1, ans+n+2-mn, ans+n+1);
	for(ll i=1;i<=n;i++) {
		printf("%lld\n",ans[i]);
	}
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:121:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
cake.cpp:123:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

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