Submission #1139287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139287		buzdi	Hacker (BOI15_hac)	C++17	100 / 100	196 ms	23932 KiB

hac

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int NMAX = 5e5;
const int INF = 2e9;

struct AINT {
    int aint[4 * NMAX + 1];
    int lazy[4 * NMAX + 1];

    void Initialize(int n) {
        for(int i = 1; i <= 4 * n; i++) {
            lazy[i] = INF;
            aint[i] = INF;
        }
    }

    void UpdateLazy(int node, int left, int right) {
        if(lazy[node] != INF) {
            aint[node] = min(aint[node], lazy[node]);
            if(left != right) {
                lazy[node * 2] = min(lazy[node * 2], lazy[node]);
                lazy[node * 2 + 1] = min(lazy[node * 2 + 1], lazy[node]);
            }
            lazy[node] = INF;
        }
    }

    void Update(int node, int left, int right, int Uleft, int Uright, int value) {
        if(left >= Uleft && right <= Uright) {
            lazy[node] = min(lazy[node], value);
            return;
        }

        UpdateLazy(node, left, right);
        int mid = (left + right) / 2;
        if(mid >= Uleft) {
            Update(node * 2, left, mid, Uleft, Uright, value);
        }
        if(mid + 1 <= Uright) {
            Update(node * 2 + 1, mid + 1, right, Uleft, Uright, value);
        }

        UpdateLazy(node * 2, mid, left);
        UpdateLazy(node * 2 + 1, mid + 1, right);
        aint[node] = max(aint[node * 2], aint[node * 2 + 1]);
    }
}aint;

int n, k;
int s, max_answer;
int answer[NMAX + 1];
int a[2 * NMAX + 1];
int sp[2 * NMAX + 1];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[n + i] = a[i];
    }
    k = n / 2 + n % 2;

    for(int i = 1; i <= 2 * n; i++) {
        sp[i] = sp[i - 1] + a[i];
    }

    aint.Initialize(n);
    for(int i = k; i - k + 1 <= n; i++) {
        int s_here = sp[i] - sp[i - k];
        // for(int j = i - k + 1; j <= i; j++) {
        //     int pos = (j > n ? j - n : j);
        //     answer[pos] = min(answer[pos], s_here);
        // }

        int left1 = i - k + 1;
        int right1 = min(i, n);
        aint.Update(1, 1, n, left1, right1, s_here);

        // cout << "% " << s_here << '\n';
        // cout << left1 << ' ' << right1 << ' ';

        if(i > n) {
            int left2 = max(n + 1, i - k + 1) - n;
            int right2 = i - n;
            // cout << left2 << ' ' << right2 << ' ';
            assert(left2 >= 1 && left2 <= n);
            assert(right2 >= 1 && right2 <= n);
            aint.Update(1, 1, n, left2, right2, s_here);
        }
        // cout << '\n';
    }
    cout << aint.aint[1]; // LOL

    return 0;
}

/*
    1 2 3 4 5 1 2 3 4 5
*/

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