Submission #1198795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198795		InvMOD	케이크 (JOI13_cake)	C++17	10 / 100	1597 ms	37704 KiB

cake

#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];

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) {
    assert(l > 0 && t >= 0 && t <= 1);
    return pref[t][r] - pref[t][l - 1];
}

ll calc(int l, int r, int Mnp) {
    int tl = Mnp - 1, tr = Mnp + 1, t = 1;
    ll res = b[Mnp];

    for (; l <= tl && tr <= r;) {
        if (!t) res += max(b[tl], b[tr]);
        (b[tl] > b[tr] ? --tl : ++tr);
        t ^= 1;
    }

    if (tl < l) {
        res += sum(tr, r, (tr & 1) ^ t);
    } else {
        res += sum(l, tl, (tl & 1) ^ t);
    }
    return res;
}

void DncIterative(int l, int r, ll conE, ll conO) {
    using T = tuple<int, int, ll, ll>;
    stack<T> stk;
    stk.emplace(l, r, conE, conO);

    while (!stk.empty()) {
        auto [cl, cr, cE, cO] = stk.top();
        stk.pop();

        if (cl > cr) continue;

        int nMnP = MnPos(cl, cr);
        ans[nMnP] = cE + calc(cl, cr, nMnP);

        if (nMnP != cl) {
            ll nconE = cE, nconO = cO;
            int bL = (!((nMnP - cl) & 1) ? (nMnP & 1) : ((nMnP & 1) ^ 1));
            nconE += sum(nMnP, cr, bL);
            nconO += sum(nMnP, cr, bL ^ 1);
            stk.emplace(cl, nMnP - 1, nconE, nconO);
        }

        if (nMnP != cr) {
            ll nconE = cE, nconO = cO;
            int bR = (!((cr - nMnP) & 1) ? (nMnP & 1) : ((nMnP & 1) ^ 1));
            nconE += sum(cl, nMnP, bR);
            nconO += sum(cl, nMnP, bR ^ 1);
            stk.emplace(nMnP + 1, cr, nconE, nconO);
        }
    }
}

void Main() {
    cin >> n;

    int cMn = 0;
    a[0] = INF;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < a[cMn]) cMn = i;
    }

    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];
        pref[0][i] += pref[0][i - 1];
        pref[1][i] += pref[1][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))]);
        }
    }

    DncIterative(2, n, (n & 1) * b[1], (!(n & 1)) * b[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];

    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);
    }

    int t = 1; while (t--) Main();
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 90