Submission #1241391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241391		tvgk	케이크 (JOI13_cake)	C++20	0 / 100	85 ms	20804 KiB

cake

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 3e5 + 7;

struct node
{
    ll sum[2];
    bool cnt;
};

node tree[mxN * 8], up;
int n, a[mxN], vt[mxN], nw[mxN];
ii arr[mxN * 2], b[mxN];
ll ans[mxN];

node Merge(node a, node b)
{
    node res;
    res.cnt = a.cnt ^ b.cnt;
    res.sum[1] = a.sum[1] + b.sum[a.cnt ^ 1];
    res.sum[0] = a.sum[0] + b.sum[a.cnt];
    return res;
}

void Build(int j = 1, int l = 1, int r = 2 * n)
{
    if (l == r)
    {
        tree[j].cnt = arr[l].se;
        tree[j].sum[1] = arr[l].fi * arr[l].se;
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    tree[j] = Merge(tree[j * 2], tree[j * 2 + 1]);
}

void Ers(int vt, int j = 1, int l = 1, int r = 2 * n)
{
    if (l > vt || vt > r)
        return;

    if (l == r)
    {
        up = Merge(up, tree[j]);
        tree[j].cnt = tree[j].sum[0] = tree[j].sum[1] = 0;
        return;
    }

    int mid = (l + r) / 2;
    Ers(vt, j * 2, l, mid);
    Ers(vt, j * 2 + 1, mid + 1, r);
    tree[j] = Merge(tree[j * 2], tree[j * 2 + 1]);
}

void Upd(int vt, int j = 1, int l = 1, int r = 2 * n)
{
    if (l > vt || vt > r)
        return;

    if (l == r)
    {
        tree[j] = up;
        return;
    }

    int mid = (l + r) / 2;
    Upd(vt, j * 2, l, mid);
    Upd(vt, j * 2 + 1, mid + 1, r);
    tree[j] = Merge(tree[j * 2], tree[j * 2 + 1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    int mn = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        b[i] = {a[i], i};
        if (a[i] < a[mn])
            mn = i;
    }
    sort(b, b + n, greater<ii>());

    int ctr = 0;
    for (int i = 1; i <= n; i++)
    {
        while (ctr < n && a[(mn + i) % n] <= b[ctr].fi)
        {
            arr[i + ctr].fi = b[ctr].fi;
            nw[b[ctr].se] = i + ctr;
            ctr++;
        }
        arr[i + ctr].fi = a[(mn + i) % n];
        arr[i + ctr].se = 1;
        vt[(mn + i) % n] = i + ctr;
    }
    Build();

    //Tinh vi tri min
    ans[mn] = a[mn];
    int cnt = 0;
    int l = (mn + n - 1) % n, r = (mn + 1) % n;
    while (l != r)
    {
        if (a[l] > a[r])
        {
            ans[mn] += a[l] * cnt;
            l = (l + n - 1) % n;
        }
        else
        {
            ans[mn] += a[r] * cnt;
            r = (r + 1) % n;
        }

        cnt ^= 1;
    }
    ans[mn] += a[l] * cnt;

    Ers(vt[mn]);
    vector<int> val;
    for (int i = 1; i < n; i++)
    {
        // Reset up
        up.cnt = 1;
        up.sum[0] = 0;
        up.sum[1] = a[mn];

        // Gop trai
        while (val.size() && val.back() <= nw[mn])
        {
            Ers(val.back());
            val.pop_back();
        }
        val.push_back(nw[mn]);

        // Cap nhat
        Upd(nw[mn]);

        mn = (mn + 1) % n;
        // Xoa vi tri hien tai
        Ers(vt[mn]);

        ans[mn] = tree[1].sum[0] + a[mn];
    }

    for (int i = 0; i < n; i++)
        cout << ans[i] << '\n';
}

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