Submission #1123446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123446		Icelast	Bigger segments (IZhO19_segments)	C++17	100 / 100	292 ms	47364 KiB

segments

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct Data{
    ll f, s;
    bool operator <(const Data &b){
        return f < b.f || (f == b.f && s > b.s);
    }
    bool operator >(const Data &b){
         return f > b.f || (f == b.f && s < b.s);
    }
};
struct IPquery{
    map<ll, Data> mp;
    void insert(ll a, Data x){
        auto it = mp.upper_bound(a);
        if(it != mp.end() && it!=mp.begin() && prev(it)->second > x){
            return;
        }
        it = mp.insert(it, {a, x});
        it->second = x;
        while(next(it) != mp.end() && next(it)->second < x){
            mp.erase(next(it));
        }
    }
    Data query(ll a){
        auto it = mp.upper_bound(a);
        return prev(it)->second;
    }
};
void chmax(pair<ll, ll> &a, pair<ll, ll> b){
    if(a.first < b.first){
        a = b;
    }else if(a.first == b.first){
        if(a.second > b.second){
            a = b;
        }
    }
}

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    vector<ll> pf(n+1, 0);
    for(int i = 1; i <= n; i++){
        pf[i] = pf[i-1]+a[i];
    }
    auto sum = [&](int l, int r) -> ll{
        return pf[r]-pf[l-1];
    };
    vector<Data> f(n+1, {-INF, 0});
    f[0] = {0, 0};
    IPquery T;
    T.insert(0, {0, 0});
    for(int i = 1; i <= n; i++){
        f[i] = T.query(pf[i]);
        f[i].f++;
        f[i].s += pf[i];
        T.insert(pf[i]+f[i].s, {f[i].f, -pf[i]});
    }
    cout << f[n].f;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

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