Submission #685067

#	Time	Username	Problem	Language	Result	Execution time	Memory
685067		stevancv	Bigger segments (IZhO19_segments)	C++14	73 / 100	993 ms	262144 KiB

segments

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int S = 30 * N;
const ll M = 1e15;
ll a[N];
pair<int, int> st[S];
int lc[S], rc[S], tsz;
void Set(int &node, ll l, ll r, ll p, int x, int y) {
    if (!node) node = ++tsz;
    if (l == r) {
        st[node] = {x, y};
        return;
    }
    ll mid = l + r >> 1;
    if (p <= mid) Set(lc[node], l, mid, p, x, y);
    else Set(rc[node], mid + 1, r, p, x, y);
    st[node] = max(st[lc[node]], st[rc[node]]);
}
pair<int, int> Get(int node, ll l, ll r, ll ql, ll qr) {
    if (r < ql || qr < l || node == 0) return st[0];
    if (ql <= l && r <= qr) return st[node];
    ll mid = l + r >> 1;
    return max(Get(lc[node], l, mid, ql, qr), Get(rc[node], mid + 1, r, ql, qr));
}
int prv[N], dp[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    st[0] = {0, -1};
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    int root = 0;
    Set(root, 0, M, 0, 0, 0);
    for (int i = 1; i <= n; i++) {
        auto u = Get(root, 0, M, 0, a[i]);
        dp[i] = u.first + 1;
        prv[i] = u.second;
        Set(root, 0, M, 2 * a[i] - a[prv[i]], dp[i], i);
    }
    cout << dp[n] << en;
    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void Set(int&, long long int, long long int, long long int, int, int)':
segments.cpp:21:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     ll mid = l + r >> 1;
      |              ~~^~~
segments.cpp: In function 'std::pair<int, int> Get(int, long long int, long long int, long long int, long long int)':
segments.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     ll mid = l + r >> 1;
      |              ~~^~~

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