Submission #1192872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192872		lopkus	Bigger segments (IZhO19_segments)	C++20	0 / 100	35 ms	78664 KiB

segments

#include <bits/stdc++.h>

#define int64_t int

const int N = 5e6 + 15;

std::pair<int, int> t[N];
std::vector<int> ll(N), rr(N);

std::pair<int, int> neutral = {-1, -1};

const int64_t MAXN = 1e15;

struct implicit {
    int idxx = 1;

    implicit() {
        for (int i = 0; i < N; i++) {
            t[i] = neutral;
        }
    }

    void update(int node, int tl, int tr, int index, std::pair<int, int> value) {
        if (tl == tr) {
            t[node] = value;
            return;
        }
        int tm = (tl + tr) / 2;
        if (index <= tm) {
            if (!ll[node]) ll[node] = ++idxx;
            update(ll[node], tl, tm, index, value);
        } else {
            if (!rr[node]) rr[node] = ++idxx;
            update(rr[node], tm + 1, tr, index, value);
        }
        t[node] = std::max((ll[node] ? t[ll[node]] : neutral), (rr[node] ? t[rr[node]] : neutral));
    }

    std::pair<int, int> query(int node, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) return neutral;
        if (l <= tl && tr <= r) return t[node];
        int tm = (tl + tr) / 2;
        std::pair<int, int> ans = neutral;
        ans = std::max(ans, query(ll[node], tl, tm, l, r));
        ans = std::max(ans, query(rr[node], tm + 1, tr, l, r));
        return ans;
    }
} seg;


void solve() {
  int n;
  std::cin >> n;
  std::vector<int64_t> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<int64_t> pref(n + 1);
  for(int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  std::vector<std::pair<int,int>> dp(n + 1, {0, 0});
  for(int i = 1; i <= n; i++) {
    seg.update(1, 0, MAXN - 1, dp[i - 1].second + pref[i - 1], dp[i - 1]);
    dp[i].first = seg.query(1, 0, MAXN - 1, 0, pref[i]).first + 1;
    dp[i].second = pref[i] - seg.query(1, 0 ,MAXN - 1, 0 , pref[i]).second;
  }
  std::cout << dp[n].first;
}


signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

Compilation message (stderr)

segments.cpp:12:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   12 | const int64_t MAXN = 1e15;
      |                      ^~~~

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