Submission #1118434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118434		Icelast	Bigger segments (IZhO19_segments)	C++17	37 / 100	259 ms	262144 KiB

segments

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
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;
        }
    }
}
struct normalize{
    vector<ll> poi, pot;
    void add(ll x){
        poi.push_back(x);
    }
    void start(){
        sort(poi.begin(), poi.end());
        if(poi.size() > 0) pot.push_back(poi[0]);
        for(int i = 1; i < (int)poi.size(); i++){
            if(poi[i] != poi[i-1]){
                pot.push_back(poi[i]);
            }
        }
    }
    int encode(ll x){
        return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
    }
};
struct ImplicitSegmentTree{
    struct Node{
        pair<ll, ll> v = {-INF, 0};
        int ln = 0, rn = 0;
    };
    ll n, N;
    vector<Node> T;
    int cnt;
    ImplicitSegmentTree(ll n): n(n){
        N = n;
        T.push_back(Node());
        T.push_back(Node());
        cnt = 1;
    };
    int new_node(){
        T.push_back(Node());
        cnt++;
        return cnt;
    }
    void down(int node, ll low, ll high){

    }
    void apply(ll i, pair<ll, ll> x){
        auto apply = [&](auto apply, int node, ll low, ll high, ll i, pair<ll, ll> x) -> void{
            down(node, low, high);
            if(low == high){
                chmax(T[node].v, x);
                down(node, low, high);
                return;
            }
            ll mid = (low+high)/2;
            if(i <= mid){
                if(T[node].ln == 0){
                    int x = new_node();
                    T[node].ln = x;
                }
                apply(apply, T[node].ln, low, mid, i, x);
            }else{
                if(T[node].rn == 0){
                    int x = new_node();
                    T[node].rn = x;
                }
                apply(apply, T[node].rn, mid+1, high, i, x);
            }
            chmax(T[node].v, T[T[node].ln].v);
            chmax(T[node].v, T[T[node].rn].v);
        };
        apply(apply, 1, 0, N, i, x);
    }
    pair<ll, ll> get(ll l, ll r){
       auto get = [&](auto self, int node, ll low, ll high, ll l, ll r) -> pair<ll, ll>{
            down(node, low, high);
            if(low > r || l > high) return {-INF, 0};
            if(low >= l && r >= high){
                return T[node].v;
            }
            ll mid = (low+high)/2;
            if(T[node].ln == 0){
                int x = new_node();
                T[node].ln = x;
            }
            if(T[node].rn == 0){
                int x = new_node();
                T[node].rn = x;
            }
            pair<ll, ll> res = {-INF, 0};
            chmax(res, self(self, T[node].ln, low, mid, l, r));
            chmax(res, self(self, T[node].rn, mid+1, high, l, r));
            chmax(T[node].v, T[T[node].ln].v);
            chmax(T[node].v, T[T[node].rn].v);
            return res;
        };
        return get(get, 1, 0, N, l, r);
    }
};
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<pair<ll, ll>> f(n+1, {-INF, 0});
    f[0] = {0, 0};
    ImplicitSegmentTree T(2e15);
    T.apply(0, {0, 0});
    for(int i = 1; i <= n; i++){
        f[i] = T.get(0, pf[i]);
        f[i].first++;
        f[i].second += pf[i];
        T.apply(pf[i]+f[i].second, {f[i].first, -pf[i]});
    }
    cout << f[n].first;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

Compilation message (stderr)

segments.cpp: In function 'void solve()':
segments.cpp:119:10: warning: variable 'sum' set but not used [-Wunused-but-set-variable]
  119 |     auto sum = [&](int l, int r) -> ll{
      |          ^~~

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