Submission #207109

#	Time	Username	Problem	Language	Result	Execution time	Memory
207109		edsa	Bigger segments (IZhO19_segments)	C++14	100 / 100	112 ms	19424 KiB

segments

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
const ll MOD = 998244353;
const int INF = 1e9+9;
const int MAXN = 1000006;

int n, a[MAXN];
ll s[MAXN];
using lii = pair<ll, ii>;
vector<lii> myStack;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s[i+1] = s[i]+a[i];
    }

    myStack.emplace_back(0, ii(0, 0));
    for (int i = 1; i <= n; i++) {
        ii maxi = (--upper_bound(myStack.begin(), myStack.end(), lii(s[i], ii(INF, INF))))->second;
        // }
        ll key = 2*s[i]-s[maxi.second];
        while (myStack.back().first >= key)
            myStack.pop_back();
        myStack.emplace_back(key, ii(maxi.first+1, i));
    }
    cout << myStack.back().second.first << endl;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27