답안 #24928

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24928 2017-06-17T08:38:09 Z khsoo01 케이크 (JOI13_cake) C++11
100 / 100
266 ms 58524 KB
#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

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]);
                      ^
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 38288 KB Output is correct
2 Correct 0 ms 38288 KB Output is correct
3 Correct 3 ms 38288 KB Output is correct
4 Correct 3 ms 38288 KB Output is correct
5 Correct 3 ms 38324 KB Output is correct
6 Correct 3 ms 38288 KB Output is correct
7 Correct 3 ms 38288 KB Output is correct
8 Correct 3 ms 38288 KB Output is correct
9 Correct 0 ms 38016 KB Output is correct
10 Correct 0 ms 38016 KB Output is correct
11 Correct 0 ms 38016 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 41176 KB Output is correct
2 Correct 49 ms 41172 KB Output is correct
3 Correct 76 ms 41204 KB Output is correct
4 Correct 166 ms 44244 KB Output is correct
5 Correct 163 ms 44244 KB Output is correct
6 Correct 203 ms 50388 KB Output is correct
7 Correct 189 ms 51308 KB Output is correct
8 Correct 193 ms 50388 KB Output is correct
9 Correct 266 ms 50388 KB Output is correct
10 Correct 226 ms 50388 KB Output is correct
11 Correct 213 ms 50892 KB Output is correct
12 Correct 189 ms 51516 KB Output is correct
13 Correct 206 ms 58524 KB Output is correct
14 Correct 176 ms 50388 KB Output is correct
15 Correct 209 ms 51400 KB Output is correct