Submission #1192568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192568		hehe	Hacker (BOI15_hac)	C++20	100 / 100	239 ms	31728 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 5e5+2;
int n;
int l[2 * MAXN], r[2 * MAXN], val[2 * MAXN];
int sums[MAXN];
int curent = 0;

void build(int now = 1){
    if (now < n) {
        build(now * 2);
        build(now * 2 + 1);
        l[now] = l[now * 2];
        r[now] = r[now * 2 + 1];
        val[now] = min(val[now * 2], val[now * 2 + 1]);
    } else {
        l[now] = curent;
        r[now] = curent;
        val[now] = sums[curent++];
    }
}

int query(int left, int right, int now = 1){
    if (right < l[now] || r[now] < left) {
        return INT32_MAX; // <-- small fix: use INT32_MAX instead of INT_MAX
    }
    if (left <= l[now] && r[now] <= right) {
        return val[now];
    }
    return min(query(left, right, now * 2), query(left, right, now * 2 + 1));
}

signed main(){
    cin >> n;
    vector<int> numere(n);

    int sum = 0, half = (n + 1) / 2;

    for (int i = 0; i < n; i++) {
        cin >> numere[i];
        if (i < half) {
            sum += numere[i];
        }
    }

    for (int i = 0; i <= n; i++) {
        sums[i % n] = sum;
        sum += numere[(i + half) % n];
        sum -= numere[i % n];
    }

    build();

    int ans = 0;

    for (int i = 0; i < n; i++) {
        int left = (i - half + 1 + n) % n;
        int right = i;
        if (right < left) {
            ans = max(ans, min(query(0, right), query(left, n - 1)));
        } else {
            ans = max(ans, query(left, right));
        }
    }

    cout << ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40