Submission #1198809

#TimeUsernameProblemLanguageResultExecution timeMemory
1198809InvMOD케이크 (JOI13_cake)C++17
100 / 100
69 ms59208 KiB
#include<bits/stdc++.h> using namespace std; #define dbg(x) "[" << #x " = " << (x) << "]" #define el "\n" using ll = long long; const int N = 3e5 + 5, lg = 19, INF = 2e9; int n, a[N], spt[lg][N]; ll pref[2][N], ans[N], b[N]; void upd(int p, ll val){ ans[p] += val; ans[p + 1] -= val; } void updR(int l, int r, ll val){ ans[l] += val, ans[r + 1] -= val; } int merge_st(int x, int y){ return b[x] < b[y] ? x : y; } int MnPos(int l, int r){ int k = 31 - __builtin_clz(r - l + 1); return merge_st(spt[k][l], spt[k][r - (1 << k) + 1]); } ll sum(int l, int r, int t){ return pref[t][r] - pref[t][l - 1]; } /* we had min(a[L] -> a[R]) > a[L - 1], a[R + 1] call MinP: minimum position of [L, R] now we will divide the segment into [L, MinP - 1], [MinP + 1, R] so we will calculate the contribute of each segment to the others with a[MinP] will be the first element we take (we have to take a[MinP] to finish) the key is to think of what we will take last */ ll calc(int l, int r, int m){ int x = l, y = r; ll ans = 0; while(x < m && m < y){ int nx = MnPos(x, m - 1); int ny = MnPos(m + 1, y); if(b[nx] < b[ny]){ // take all [nx + 1, y] before take [x, nx] int t = (((y - nx) & 1) ^ (nx & 1)); ans = ans + sum(x, nx, t); x = nx + 1; } else{ // take all [x, ny - 1] before take [ny, y] int t = (((ny - x) & 1) ^ (ny & 1)); ans = ans + sum(ny, y, t); y = ny - 1; } } ans = ans + (y <= m ? sum(x, m, (m&1)) : (sum(m, y, (m&1)))); return ans; } void Dnc(int l, int r){ if(l > r) return; int nMnP = MnPos(l, r); upd(nMnP, calc(l, r, nMnP)); Dnc(nMnP + 1, r); Dnc(l, nMnP - 1); int bL = (!((nMnP - l) & 1) ? (nMnP & 1) : ((nMnP & 1) ^ 1)); updR(l, nMnP - 1, sum(nMnP, r, bL)); int bR = (!((r - nMnP) & 1) ? (nMnP & 1) : ((nMnP & 1) ^ 1)); updR(nMnP + 1, r, sum(l, nMnP, bR)); } void Main() { cin >> n; int cMn = 0; a[0] = INF; for(int i = 1; i <= n; i++){ cin >> a[i]; cMn = (a[i] < a[cMn] ? i : cMn); } { int i = 1, j = cMn; while(i <= n){ b[i] = a[j], spt[0][i] = i; (i&1 ? pref[1][i] : pref[0][i]) += b[i]; for(int t = 0; t < 2; t++) pref[t][i] += pref[t][i - 1]; i++; j = (j + 1 > n ? j + 1 - n : j + 1); } for(int i = 1; i < lg; i++){ for(int j = 1; j + (1 << i) - 1 <= n; j++){ spt[i][j] = merge_st(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]); } } Dnc(2, n); } if(n&1) updR(2, n, b[1]); for(int i = 2; i <= n; i++) ans[i] += ans[i - 1]; { // Calculate ans[1] int l = n, r = 2, state = 1; ans[1] += b[1]; while(l != r){ if(!state) ans[1] += max(b[l], b[r]); (b[l] > b[r] ? --l : ++r); state ^= 1; } if(!state) ans[1] += b[l]; } { for(int i = 1; i <= n; i++) b[i] = ans[i]; int i = cMn, j = 1; while(j <= n){ ans[i] = b[j]; j++; i = (i + 1 > n ? 1 : i + 1); } } for(int i = 1; i <= n; i++){ cout << ans[i] << el; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define name "InvMOD" if(fopen(name".INP", "r")){ freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout); } //system("brute.exe"); int t = 1; while(t--) Main(); return 0; }

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...