Submission #12976

#TimeUsernameProblemLanguageResultExecution timeMemory
12976ainta케이크 (JOI13_cake)C++98
0 / 100
4 ms27528 KiB
#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){ if ((e - b + 1) % 2 == 0)Res[a] += SS[x][0]; else Res[a] += SS[x][1]; } 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; 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; for (i = 1; i < c1; i++)Do(p1[i + 1] + 1, p1[i] - 1); for (i = 1; i < c2; i++)Do(p2[i] + 1, p2[i + 1] - 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...