Submission #711202

#	Time	Username	Problem	Language	Result	Execution time	Memory
711202		Thienu	Bigger segments (IZhO19_segments)	C++17	13 / 100	1 ms	340 KiB

segments

#include <bits/stdc++.h>

using namespace std;

#define u_map unordered_map
#define u_set unordered_set
#define u_multiset unordered_multiset

using ll = long long;
using vvi = vector<vector<int>>;
using vi = vector<int>;
using vvll = vector<vector<long long>>;
using vll = vector<long long>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> &r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif

const ll INF = 1e18;

struct Node {
    Node *l, *r;
    int lo, hi;
    ll vmin;

    void update(){
        vmin = min(l->vmin, r->vmin);
    }

    Node(int lo, int hi, ll id=INF) : lo(lo), hi(hi){
        if(lo + 1 == hi){
            vmin = id;
        } else {
            int mid = lo + (hi - lo) / 2;
            l = new Node(lo, mid, id);
            r = new Node(mid, hi, id);
            update();
        }
    }

    // vals[i] = x
    void set(int i, ll x){
        if(i < lo || hi <= i){
            return;
        }
        if(lo + 1 == hi){
            vmin = x;
        } else {
            l->set(i, x);
            r->set(i, x);
            update();
        }
    }

    // greatest i such that vals[i] <= d
    // -1 otherwise
    int query(int d) {
        if(vmin > d) return -1;
        if(lo + 1 == hi) return lo;
        if(r->vmin <= d) return r->query(d);
        else return l->query(d);
    }
};

void solve(){
    int n;
    cin >> n;
    vll v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    vll pref(n+1);
    for(int i = 1; i <= n; i++) pref[i] = pref[i-1] + v[i-1];

    Node* st = new Node(0, n+1);
    st->set(0, 0);

    vi dp(n+1, 1e9);
    dp[0] = 0;

    for(int i = 1; i <= n; i++){
        int idx = st->query(pref[i]);
        dp[i] = dp[idx] + 1;
        debug(i, idx, pref[i] - pref[idx]);
        st->set(i, 2LL * pref[i] - pref[idx]);
    }

    debug(dp);
    cout << dp[n] << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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