Submission #1192555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192555		hehe	Hacker (BOI15_hac)	C++20	0 / 100	0 ms	324 KiB

hac

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

int n;
int l[500004], r[500004], val[500004];
vector<int>sums;
int become = 0;

void build(int now){
    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] = become;
        r[now] = become;
        val[now] = sums[become++];
    }
}

int query(int left, int right, int now){
    if(right < l[now] || r[now] < left){
        return INT_MAX;
    }
    else if(left <= l[now] && right >= r[now]){
        return val[now];
    }
    else{
        return(min(query(left, right, now * 2), query(left, right, now * 2 + 1)));
    }
}

signed main(){
    int left, right;
    cin >> n;
    vector<int>numere;
    
    int sum = 0, half = (n + 1) / 2, add;
    
    for(int i = 0; i < n; i++){
        cin >> add;
        numere.push_back(add);
        if(i < half){
            sum+= add;
        }
    }
    
    sums.resize(n + 1);
    for(int i = 0; i <= n; i++){
        sums[i%n] = sum;
        
        sum -= numere[(i + half)%n];
        sum += numere[i%n];
    }
    
    build(1);
    
    int ans = -1;
    
    for(int i = 0; i < n; i++){
        left = (i - half + 1) % n;
        right = i;
        if(right < left){
            ans = max(ans, min(query(0, right, 1), query(left, n - 1, 1)));
        }
        else{
            ans = max(ans, query(left, right, 1));
        }
    }
    
    cout << ans;
}

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