| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12977 |
2015-01-22T18:28:58 Z |
ainta |
케이크 (JOI13_cake) |
C++ |
|
256 ms |
27528 KB |
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N_ 301000
#define INF 1999999999
#define SZ 524288
int n, w[N_], TP[N_];
int p1[N_], p2[N_];
int Match[N_], Next2[N_], Prev2[N_];
long long Sum[N_][2];
long long Res[N_], SS[N_][2];
void Pro1(int b, int m, int e){
int pv1 = m, pv2 = m + 1, c = 0, i;
long long S1 = 0, S2 = 0;
while (pv1 >= b || pv2 <= e){
c++;
if (w[pv1] > w[pv2]){
SS[pv1][0] = S1, SS[pv1][1] = S2;
if (c & 1)S1 += w[pv1];
else S2 += w[pv1];
Match[pv1] = pv2 - 1;
pv1--;
}
else{
SS[pv2][0] = S1, SS[pv2][1] = S2;
if (c & 1)S1 += w[pv2];
else S2 += w[pv2];
Match[pv2] = pv1 + 1;
pv2++;
}
}
Match[b - 1] = e, Match[e + 1] = b;
for (i = b; i <= e; i++){
SS[i][0] = S1 - SS[i][0];
SS[i][1] = S2 - SS[i][1];
if ((Match[i] + i) % 2 == 1)swap(SS[i][0], SS[i][1]);
}
}
long long Calc(int s, int l, int ck){
if (s <= l)return Sum[l][(s & 1) ^ ck] - Sum[s - 1][(s & 1) ^ ck];
return Sum[s][(s & 1) ^ ck] - Sum[l - 1][(s & 1) ^ ck];
}
void Add1(int a, int b, int e, int s, int l){
Res[a] += Calc(s, l, (e - b + 1) & 1);
}
void Add2(int a, int b, int e, int x){
Res[a] += SS[x][(e - b + 1) % 2];
}
void Do(int b, int e){
if (e < b)return;
if (b == e){
Res[b] += w[b];
return;
}
int m = (b + e) >> 1, i, c1 = 0, c2 = 0, M = INF, j, t;
for (i = m; i >= b - 1; i--){
if (M > w[i]){
M = w[i];
if (i != m) Do(i + 1, t);
t = i - 1;
}
}
M = INF;
for (i = m + 1; i <= e + 1; i++){
if (M > w[i]){
M = w[i];
if (i != m + 1)Do(t, i - 1);
t = i + 1;
}
}
c1 = c2 = 0; M = INF;
for (i = m; i >= b; i--){
if (M > w[i])M = w[i], p1[++c1] = i;
}
M = INF;
for (i = m + 1; i <= e; i++){
if (M > w[i])M = w[i], p2[++c2] = i;
}
p1[++c1] = b - 1, p2[++c2] = e + 1;
Pro1(b, m, e);
for (i = 1; i < c1; i++){
for (j = p1[i + 1] + 1; j <= p1[i] - 1; j++){
Add1(j, p1[i + 1] + 1, p1[i] - 1, p1[i], Match[p1[i + 1]]);
Add2(j, p1[i + 1] + 1, Match[p1[i + 1]], p1[i + 1]);
}
}
for (i = 1; i < c2; i++){
for (j = p2[i] + 1; j <= p2[i + 1] - 1; j++){
Add1(j, p2[i] + 1, p2[i + 1] - 1, p2[i], Match[p2[i + 1]]);
Add2(j, Match[p2[i + 1]], p2[i + 1] - 1, p2[i + 1]);
}
}
for (i = 1; i < c1; i++){
int ed = p1[i];
for (j = p1[i] - 1; j >= p1[i + 1]; j--){
Add1(p1[i], j + 2, ed, j + 1, j + 1);
if (j == p1[i + 1])t = Match[j];
else t = Next2[j] - 1;
if (ed < t){
Add1(p1[i], j + 1, ed, ed + 1, t);
ed = t;
}
}
Add2(p1[i], p1[i + 1] + 1, Match[p1[i + 1]], p1[i + 1]);
}
for (i = 1; i < c2; i++){
int be = p2[i];
for (j = p2[i] + 1; j <= p2[i + 1]; j++){
Add1(p2[i], be, j - 2, j - 1, j - 1);
if (j == p2[i + 1])t = Match[j];
else t = Prev2[j] + 1;
if (be > t){
Add1(p2[i], be, j - 1, be - 1, t);
be = t;
}
}
Add2(p2[i], Match[p2[i + 1]], p2[i + 1] - 1, p2[i + 1]);
}
}
struct order{
int a, num;
bool operator<(const order &p)const{
return a < p.a;
}
}ord[N_];
int IT[SZ * 2 + 2];
void Add(int a){
a += SZ;
while (a){
IT[a]++;
a >>= 1;
}
}
int Gap1(int b){
b += SZ;
int e = SZ + SZ - 1, r = 0;
while (b <= e){
if (b & 1){
if (r + IT[b] >= 2)break;
r += IT[b];
}
b = (b + 1) >> 1, e = (e - 1) >> 1;
}
if (b > e)return n + 1;
while (b < SZ){
if (IT[b * 2] >= 2 - r)b = b * 2;
else{
r += IT[b * 2];
b = b * 2 + 1;
}
}
return b - SZ;
}
int Gap2(int e){
e += SZ;
int b = SZ, r = 0;
while (b <= e){
if (!(e & 1)){
if (r + IT[e] >= 2)break;
r += IT[e];
}
b = (b + 1) >> 1, e = (e - 1) >> 1;
}
if (b > e)return 0;
while (e < SZ){
if (IT[e * 2 + 1] >= 2 - r)e = e * 2 + 1;
else{
r += IT[e * 2 + 1];
e = e * 2;
}
}
return e - SZ;
}
void PrePro(){
int i;
for (i = 1; i <= n; i++){
ord[i].a = w[i], ord[i].num = i;
}
sort(ord + 1, ord + n + 1);
for (i = 1; i <= n; i++){
Next2[ord[i].num] = Gap1(ord[i].num + 1);
Prev2[ord[i].num] = Gap2(ord[i].num - 1);
Add(ord[i].num);
}
}
int main(){
int i, M, st, pv1, pv2, tp;
scanf("%d", &n);
for (i = 1; i <= n; i++){
scanf("%d", &w[i]);
if (i == 1 || M > w[i]){
M = w[i], st = i;
}
}
for (i = 1; i <= st; i++)TP[i] = w[i];
for (i = 1; i <= n - st; i++)w[i] = w[i + st];
for (i = n - st + 1; i <= n; i++)w[i] = TP[i - n + st];
pv1 = 1, pv2 = n - 1;
Res[n] = w[n];
tp = w[n];
M = 0;
while (pv1 <= pv2){
M++;
if (w[pv1] < w[pv2]){
if (M % 2 == 0)Res[n] += w[pv2];
pv2--;
}
else{
if (M % 2 == 0)Res[n] += w[pv1];
pv1++;
}
}
w[0] = w[n] = 0;
n--;
PrePro();
for (i = 1; i <= n; i++){
Sum[i][0] = Sum[i - 1][0], Sum[i][1] = Sum[i - 1][1];
Sum[i][i % 2] += w[i];
}
Do(1, n);
if (n % 2 == 0){
for (i = 1; i <= n; i++)Res[i] += tp;
}
n++;
for (i = n - st + 1; i <= n; i++)printf("%lld\n", Res[i]);
for (i = 1; i <= n - st; i++)printf("%lld\n", Res[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
27528 KB |
Output is correct |
| 2 |
Correct |
4 ms |
27528 KB |
Output is correct |
| 3 |
Correct |
4 ms |
27528 KB |
Output is correct |
| 4 |
Correct |
4 ms |
27528 KB |
Output is correct |
| 5 |
Correct |
4 ms |
27528 KB |
Output is correct |
| 6 |
Correct |
0 ms |
27528 KB |
Output is correct |
| 7 |
Correct |
4 ms |
27528 KB |
Output is correct |
| 8 |
Correct |
4 ms |
27528 KB |
Output is correct |
| 9 |
Correct |
0 ms |
27528 KB |
Output is correct |
| 10 |
Correct |
0 ms |
27528 KB |
Output is correct |
| 11 |
Correct |
0 ms |
27528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
27528 KB |
Output is correct |
| 2 |
Correct |
68 ms |
27528 KB |
Output is correct |
| 3 |
Correct |
68 ms |
27528 KB |
Output is correct |
| 4 |
Correct |
200 ms |
27528 KB |
Output is correct |
| 5 |
Correct |
164 ms |
27528 KB |
Output is correct |
| 6 |
Correct |
228 ms |
27528 KB |
Output is correct |
| 7 |
Correct |
176 ms |
27528 KB |
Output is correct |
| 8 |
Correct |
204 ms |
27528 KB |
Output is correct |
| 9 |
Correct |
256 ms |
27528 KB |
Output is correct |
| 10 |
Correct |
192 ms |
27528 KB |
Output is correct |
| 11 |
Correct |
188 ms |
27528 KB |
Output is correct |
| 12 |
Correct |
208 ms |
27528 KB |
Output is correct |
| 13 |
Correct |
204 ms |
27528 KB |
Output is correct |
| 14 |
Correct |
160 ms |
27528 KB |
Output is correct |
| 15 |
Correct |
208 ms |
27528 KB |
Output is correct |
