| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 295365 |
2020-09-09T15:56:46 Z |
송준혁(#5805) |
케이크 (JOI13_cake) |
C++17 |
|
94 ms |
7416 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define INF (1ll<<62)
#define MOD 1'000'000'007
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N;
int A[303030], B[303030];
pii T[1202020];
LL O[303030], E[303030], S[303030];
void init(int id, int s, int e){
if (s == e){T[id]=pii(A[s], s); return;}
int m=s+e>>1;
init(id*2, s, m), init(id*2+1, m+1, e);
T[id] = min(T[id*2], T[id*2+1]);
}
pii rmq(int id, int s, int e, int ts, int te){
if (e < ts || te < s) return pii(MOD, 0);
if (ts <= s && e <= te) return T[id];
int m=s+e>>1;
return min(rmq(id*2, s, m, ts, te), rmq(id*2+1, m+1, e, ts, te));
}
int lb(int id, int s, int e, int ts, int te, int v){
if (e < ts || te < s || T[id].fi > v) return te+1;
if (s == e) return s;
int m=s+e>>1;
int r = lb(id*2, s, m, ts, te, v);
if (r<=te) return r;
return lb(id*2+1, m+1, e, ts, te, v);
}
int rb(int id, int s, int e, int ts, int te, int v){
if (e < ts || te < s || T[id].fi > v) return ts-1;
if (s == e) return s;
int m=s+e>>1;
int r = rb(id*2+1, m+1, e, ts, te, v);
if (r>=ts) return r;
return rb(id*2, s, m, ts, te, v);
}
void f(int s, int e){
if (s > e) return;
int m = rmq(1, 1, N-1, s, e).se;
f(s, m-1);
if ((2*m-s+1)&1) S[s]+=E[e]-E[m-1], S[m]-=E[e]-E[m-1];
else S[s]+=O[e]-O[m-1], S[m]-=O[e]-O[m-1];
f(m+1, e);
if ((e+1)&1) S[m+1]+=E[m]-E[s-1], S[e+1]-=E[m]-E[s-1];
else S[m+1]+=O[m]-O[s-1], S[e+1]-=O[m]-O[s-1];
LL sum=A[m];
int t=1;
if (m-s < e-m){
int x=m+1;
for (int i=m-1; i>=s; i--){
int nx = lb(1, 1, N-1, x, e, A[i]);
if ((t+x+1)&1) sum+=E[nx-1]-E[x-1];
else sum+=O[nx-1]-O[x-1];
t += nx-x, x=nx;
if ((t+1)&1) sum += A[i];
t++;
}
}
else{
int x=m-1;
for (int i=m+1; i<=e; i++){
int nx = rb(1, 1, N-1, s, x, A[i]);
if ((t+x+1)&1) sum+=E[x]-E[nx];
else sum+=O[x]-O[nx];
t += x-nx, x=nx;
if ((t+1)&1) sum += A[i];
t++;
}
}
S[m]+=sum, S[m+1]-=sum;
}
int main(){
int mn=0;
scanf("%d", &N);
for (int i=0; i<N; i++){
scanf("%d", &B[i]);
if (B[mn] > B[i]) mn = i;
}
for (int i=0; i<N; i++) A[i] = B[(i+mn)%N];
for (int i=1; i<N; i++){
O[i]=O[i-1], E[i]=E[i-1];
if (i&1) O[i] += A[i];
else E[i] += A[i];
}
init(1, 1, N-1);
f(1, N-1);
if (N&1) S[1] += A[0];
for (int i=1; i<N; i++) S[i] += S[i-1];
int l=1, r=N-1, t=0;
S[0] = A[0];
while (l<=r){
if (A[l] < A[r]){
if (t&1) S[0] += A[r];
r--;
}
else{
if (t&1) S[0] += A[l];
l++;
}
t++;
}
for (int i=0; i<N; i++) printf("%lld\n", S[(i-mn+N)%N]);
return 0;
}
Compilation message
cake.cpp: In function 'void init(int, int, int)':
cake.cpp:18:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int m=s+e>>1;
| ~^~
cake.cpp: In function 'pii rmq(int, int, int, int, int)':
cake.cpp:26:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
26 | int m=s+e>>1;
| ~^~
cake.cpp: In function 'int lb(int, int, int, int, int, int)':
cake.cpp:33:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int m=s+e>>1;
| ~^~
cake.cpp: In function 'int rb(int, int, int, int, int, int)':
cake.cpp:42:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int m=s+e>>1;
| ~^~
cake.cpp: In function 'int main()':
cake.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
cake.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
88 | scanf("%d", &B[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
