Submission #723875

#	Time	Username	Problem	Language	Result	Execution time	Memory
723875		OttincaM	Hacker (BOI15_hac)	C++17	100 / 100	227 ms	117840 KiB

hac

#include <iostream>
#include <vector>
#include "stdio.h"

using namespace std;
#define int long long






//
// Created by Otabek Jurabekov on 4/12/22.
//

template <typename Type> struct SegTree{
    int Sz; 
    vector <Type> t, arr; 
    SegTree(int _n, Type _m){
        t.assign((_n + 1) * 4 + 7, _m); 
        Sz = _n;
    }
    Type com(Type F, Type S){
        return max(F, S);
    }
    
    void BuildTree(int v, int l, int r, vector <Type> &Array){
        arr = Array; build(v, l, r);
    }

    void build(int v, int l, int r){
        if(l == r){
            t[v] = arr[l]; return;
        }
        int m = (l + r) >> 1;
        build(v << 1, l, m); build(v << 1 | 1, m + 1, r);
        t[v] = com(t[v << 1], t[v << 1 | 1]);
    }

    void upd_put_one(int v, int tl, int tr, int idx, Type del){
        if(tl == tr){
            t[v] = del; return;
        }
        int tm = (tl + tr) >> 1;
        if(idx > tm) upd_put_one(v << 1 | 1, tm + 1, tr, idx, del);
        else upd_put_one(v << 1, tl, tm, idx, del);
        t[v] = com(t[v << 1], t[v << 1 | 1]);
    }

    void upd_add_one(int v, int tl, int tr, int idx, Type del){
        if(tl == tr){
            t[v] += del; return;
        }
        int tm = (tl + tr) >> 1;
        if(idx > tm) upd_add_one(v << 1 | 1, tm + 1, tr, idx, del);
        else upd_add_one(v << 1, tl, tm, idx, del);
        t[v] = com(t[v << 1], t[v << 1 | 1]);
    }

    Type get_one(int v, int tl, int tr, int idx){
        if(tl == tr){
            return t[v];
        }
        int tm = (tl + tr) >> 1;
        if(idx > tm) return t[v] + get_one(v << 1 | 1, tm + 1, tr, idx);
        return t[v] + get_one(v << 1, tl, tm, idx);
    }

    Type get_lr(int v, int tl, int tr, int l, int r){
        if(tl >= l && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        if(tm < l) return get_lr(v << 1 | 1, tm + 1, tr, l, r);
        if(tm >= r) return get_lr(v << 1, tl, tm, l, r);
        return com(get_lr(v << 1, tl, tm, l, r), get_lr(v << 1 | 1, tm + 1, tr, l, r));
    }
    
    
    
    void upd_put_one(int idx, Type del){upd_put_one(1, 1, Sz, idx, del);}
    void upd_add_one(int idx, Type del){upd_add_one(1, 1, Sz, idx, del);}
    Type get_lr(int l, int r){return get_lr(1, 1, Sz, l, r);}
    Type get_one(int idx){return get_one(1, 1, Sz, idx);}
};








signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    #ifdef WTF
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        freopen("error.txt", "w", stderr);
    #endif
 
    int n; cin >> n;
    vector <int> a(2 * n + 2);
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        a[i + n] = a[i];
    }

    vector <int> pr(2 * n + 2, 0), sf(2 * n + 2, 0), P(2 * n + 2, 0), S(2 * n + 2, 0);
    for(int i = 1; i <= n * 2; i ++){
        pr[i] = pr[i - 1] + a[i];
        P[i] = pr[i];
        if(i - n / 2 >= 1) P[i] -= pr[i - n / 2];
    }  
    for(int i = n * 2; i >= 1; i --){
        sf[i] = sf[i + 1] + a[i];
        S[i] = sf[i];
        if(i + n / 2 <= 2 * n) S[i] -= sf[i + n / 2];
    }
    int K = n + n;
    SegTree <int> SF(K, 0), PR(K, 0);
    SF.BuildTree(1, 1, K, S);
    PR.BuildTree(1, 1, K, P);


    int ans = 0;
    for(int i = 1; i <= n; i ++){
        int mxs = n - (n / 2 - (i - 1)) + 1;
        if(n / 2 - (i - 1) <= 0) mxs = n;
        int mnp = (n / 2 - (n - i));
        mnp = max(mnp, 1LL);
        int cnt = 0;
        if(mnp <= i - 1) cnt = PR.get_lr(1, 1, K, mnp, i - 1);
        if(i + 1 <= mxs) cnt = max(cnt, SF.get_lr(1, 1, K, i + 1, mxs));
        ans = max(ans, pr[n] - cnt);
    }
    cout << ans << "\n";
    return 0;
}

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