| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 24928 |
2017-06-17T08:38:09 Z |
khsoo01 |
케이크 (JOI13_cake) |
C++11 |
|
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]);
^
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
