oj.uz

Submission #372791

# Submission time Handle Problem Language Result Execution time Memory
372791 2021-03-01T17:19:13 Z two_sides 케이크 (JOI13_cake) C++17
100 / 100
 135 ms 56428 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 300005;
const int LG = 19;

int a[N], b[N], rmq[LG][N], lg[N], ID[N];
long long ans[N], sum[2][N];

int getMin(int l, int r) {
    int k = lg[r - l + 1];
    return a[rmq[k][l]] <
    a[rmq[k][r + 1 - (1 << k)]] ?
    rmq[k][l] : rmq[k][r + 1 - (1 << k)];
}

long long getSum(int prt, int l, int r) {
    return sum[prt][r] - sum[prt][l - 1];
}

void solve(int lef, int rig, long long cur) {
    int mid = getMin(lef, rig);
    ans[ID[mid]] += cur + a[mid];
    for (int l = lef, r = rig;
    l < mid || r > mid; ) {
        int minP = 0;
        if (l < mid) {
            int p = getMin(l, mid - 1);
            if (a[minP] > a[p]) minP = p;
        }
        if (r > mid) {
            int p = getMin(mid + 1, r);
            if (a[minP] > a[p]) minP = p;
        }
        if (minP < mid) {
            ans[ID[mid]] += getSum
            ((minP ^ (r - minP)) & 1, l, minP);
            l = minP + 1;
        }
        else {
            ans[ID[mid]] += getSum
            ((minP ^ (minP - l)) & 1, minP, r);
            r = minP - 1;
        }
    }
    if (lef < mid) solve(lef, mid - 1, cur +
    getSum((mid ^ (mid - lef)) & 1, mid, rig));
    if (mid < rig) solve(mid + 1, rig, cur +
    getSum((mid ^ (rig - mid)) & 1, lef, mid));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, minP = 1; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < a[minP]) minP = i;
    }
    /// remove minimum
    {
        int m = 0;
        for (int i = minP % n + 1;
        i != minP; i = i % n + 1) {
            b[++m] = a[i]; ID[m] = i;
        }
        ans[minP] = a[minP];
        if (n & 1)
            for (int i = 1; i <= n; i++)
                if (i != minP) ans[i] = a[minP];
        n = m; swap(a, b);
        int l = 1, r = n;
        for (int i = 0; i < n; i++) {
            if (a[l] > a[r]) {
                if (i & 1) ans[minP] += a[l];
                l++;
            }
            else {
                if (i & 1) ans[minP] += a[r];
                r--;
            }
        }
    }
    // prepare
    {
        rmq[0][1] = 1; a[0] = INT_MAX;
        for (int i = 2; i <= n; i++) {
            rmq[0][i] = i; lg[i] = lg[i / 2] + 1;
        }
        for (int k = 1; k < LG; k++)
            for (int i = 1; i + (1 << k) <= n + 1; i++)
                rmq[k][i] = a[rmq[k - 1][i]] <
                a[rmq[k - 1][i + (1 << k - 1)]] ?
                rmq[k - 1][i] : rmq[k - 1][i + (1 << k - 1)];
        for (int i = 1; i <= n; i++) {
            sum[0][i] = sum[0][i - 1];
            sum[1][i] = sum[1][i - 1];
            sum[i & 1][i] += a[i];
        }
    }
    solve(1, n, 0);
    for (int i = 1; i <= n + 1; i++)
        cout << ans[i] << '\n';
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:93:42: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   93 |                 a[rmq[k - 1][i + (1 << k - 1)]] ?
      |                                        ~~^~~
cake.cpp:94:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   94 |                 rmq[k - 1][i] : rmq[k - 1][i + (1 << k - 1)];
      |                                                      ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3436 KB Output is correct
2 Correct 4 ms 3308 KB Output is correct
3 Correct 5 ms 3436 KB Output is correct
4 Correct 4 ms 3308 KB Output is correct
5 Correct 5 ms 3584 KB Output is correct
6 Correct 5 ms 3320 KB Output is correct
7 Correct 4 ms 3308 KB Output is correct
8 Correct 5 ms 3328 KB Output is correct
9 Correct 3 ms 2668 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 14800 KB Output is correct
2 Correct 38 ms 14700 KB Output is correct
3 Correct 41 ms 14828 KB Output is correct
4 Correct 97 ms 31340 KB Output is correct
5 Correct 81 ms 27116 KB Output is correct
6 Correct 121 ms 39916 KB Output is correct
7 Correct 115 ms 41912 KB Output is correct
8 Correct 117 ms 39976 KB Output is correct
9 Correct 122 ms 39788 KB Output is correct
10 Correct 113 ms 39876 KB Output is correct
11 Correct 113 ms 41068 KB Output is correct
12 Correct 113 ms 42604 KB Output is correct
13 Correct 126 ms 56428 KB Output is correct
14 Correct 105 ms 39788 KB Output is correct
15 Correct 135 ms 42092 KB Output is correct