Submission #1198784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198784		InvMOD	케이크 (JOI13_cake)	C++17	10 / 100	1596 ms	37192 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){
    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 Mnp){
    int tl = Mnp - 1, tr = Mnp + 1, t = 1; ll ans = b[Mnp];

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

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

void Dnc(int l, int r, ll conE, ll conO){
    if(l > r) return;

    int nMnP = MnPos(l, r);
    ans[nMnP] = conE + calc(l, r, nMnP);

    ll nconE = conE, nconO = conO;
    
    int bL = (!((nMnP - l) & 1) ? (nMnP & 1) : ((nMnP & 1) ^ 1));
    nconE += sum(nMnP, r, bL);
    nconO += sum(nMnP, r, bL ^ 1);
    Dnc(l, nMnP - 1, nconE, nconO);

    nconE = conE, nconO = conO;
    
    int bR = (!((r - nMnP) & 1) ? (nMnP & 1) : ((nMnP & 1) ^ 1));
    nconE += sum(l, nMnP, bR);
    nconO += sum(l, nMnP, bR ^ 1);
    Dnc(nMnP + 1, r, nconE, nconO);
}

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, (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];

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

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

Compilation message (stderr)

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

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