Submission #402842

#	Time	Username	Problem	Language	Result	Execution time	Memory
402842		gevacrt	Hacker (BOI15_hac)	C++17	100 / 100	411 ms	22340 KiB

hac

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

template<class T, void UPDATE(T&, T), T MERGE(T, T)>
struct SEGMENT_TREE {
    int range_l, range_r;
    vector<T> V, lazy; T DEF;

    SEGMENT_TREE(int l, int r, T def = T{}){
        DEF = def;
        V.resize(4*(r-l+1), DEF);
        lazy.resize(4*(r-l+1), DEF);
        range_l = l, range_r = r;
    }

    void lazyUpdate(int n, int l, int r){
        if(lazy[n] == DEF) return;
        UPDATE(V[n], lazy[n]);
        if(l < r){
            UPDATE(lazy[2*n], lazy[n]);
            UPDATE(lazy[2*n+1], lazy[n]);
        }
        lazy[n] = DEF;
    }

    void update(int n, int l, int r, int L, int R, T val){
        lazyUpdate(n, l, r);
        if(r < L or R < l) return;
        if(L <= l and r <= R){
            UPDATE(lazy[n], val);
            lazyUpdate(n, l, r);
            return;
        }

        int m = (l+r)/2;
        update(n*2, l, m, L, R, val);
        update(n*2+1, m+1, r, L, R, val);
        V[n] = MERGE(V[n*2], V[n*2+1]);
    }

    T query(int n, int l, int r, int L, int R){
        lazyUpdate(n, l, r);
        if(r < L or R < l) return DEF;
        if(L <= l and r <= R) return V[n];

        int m = (l+r)/2;
        return MERGE(query(n*2, l, m, L, R),
        query(n*2+1, m+1, r, L, R));
    }

    void update(int L, T val){
        update(1, range_l, range_r, L, L, val);
    }
    T query(int L, int R){
        if(L <= R) return query(1, range_l, range_r, L, R);
        return min(query(1, range_l, range_r, L, range_r),
            query(1, range_l, range_r, 0, R)); 
    }
};

void seg_upd(int &a, int b){a = b;}
int seg_merge(int a, int b){return min(a, b);}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N; cin >> N;
    vi V(N); for(auto &i : V) cin >> i;

    auto bb = [&](int x){
        return (x+N)%N;
    };

    vi sum(N); int sz = (N+1)/2;
    sum[sz-1] = accumulate(V.begin(), V.begin()+sz, 0);

    for(int x = sz; x != sz-1; x = bb(x+1)){
        sum[x] = V[x]+sum[bb(x-1)]-V[bb(x-sz)];
    }

    SEGMENT_TREE<int, seg_upd, seg_merge> ST(0, N-1, INF);
    for(int x = 0; x < N; x++) ST.update(x, sum[x]); 

    int ans = 0;
    for(int x = 0; x < N; x++)
        ans = max(ans, ST.query(x, bb(x+sz-1)));

    cout << ans << endl;

    return 0;
}

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