Submission #933516

#	Time	Username	Problem	Language	Result	Execution time	Memory
933516		vjudge1	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	6492 KiB

segments

/* In the name of God */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld EPS = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int _add(int a, int b){ int res = a + b; return (res >= MOD ? res - MOD : res); }
inline int _neg(int a, int b){ int res = (abs(a - b) < MOD ? a - b : (a - b) % MOD); return (res < 0 ? res + MOD : res); }
inline int _mlt(ll a, ll b){ return (a * b % MOD); }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 5e5 + 5;

PII seg[MAXN << 2], laz[MAXN << 2];
#define lc id << 1
#define rc id << 1 | 1

void build(int id, int l, int r){
    if (r - l == 1){
        seg[id] = MP(0, 0);
        laz[id] = MP(-1, -1);
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid, r);
    seg[id] = seg[lc];
    laz[id] = laz[lc];
}

void shift(int id, int l, int r){
    if (laz[id].first == -1) return;
    laz[lc] = max(laz[lc], laz[id]);
    laz[rc] = max(laz[rc], laz[id]);
    seg[lc] = max(seg[lc], laz[id]);
    seg[rc] = max(seg[rc], laz[id]);
    laz[id] = MP(-1, -1);
}

void upd(int id, int l, int r, int ql, int qr, PII x){
    if (ql >= r || qr <= l) return;
    if (l >= ql && r <= qr){
        seg[id] = max(seg[id], x);
        laz[id] = max(laz[id], x);
        return;
    }
    int mid = l + r >> 1;
    shift(id, l, r);
    upd(lc, l, mid, ql, qr, x);
    upd(rc, mid, r, ql, qr, x);
    seg[id] = max(seg[lc], seg[rc]);
}

PII get(int id, int l, int r, int ql, int qr){
    if (ql >= r || qr <= l) return MP(0, 0);
    if (l >= ql && r <= qr) return seg[id];
    int mid = l + r >> 1;
    shift(id, l, r);
    return max(get(lc, l, mid, ql, qr), get(rc, mid, r, ql, qr));
}

int a[MAXN];
ll ps[MAXN];
PII dp[MAXN];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        ps[i] = ps[i - 1] + a[i];
    }
    build(1, 1, n + 1);
    upd(1, 1, n + 1, 1, n + 1, MP(1, 1));
    for (int i = 1; i <= n; i++){
        dp[i] = get(1, 1, n + 1, i, i + 1);
        ll s = ps[i] - ps[dp[i].second - 1];
        if (ps[n] - ps[i] < s) continue;
        if (a[i + 1] >= s) upd(1, 1, n + 1, i + 1, n + 1, MP(dp[i].first + 1, i + 1));
        else {
            int l = i + 1, r = n;
            while (r - l > 1){
                int mid = l + r >> 1;
                if (ps[mid] - ps[i + 1] >= s) r = mid;
                else l = mid;
            }
            upd(1, 1, n + 1, r, n + 1, MP(dp[i].first + 1, r));
        }
    }
    cout << dp[n].first;
    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void build(int, int, int)':
segments.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = l + r >> 1;
      |               ~~^~~
segments.cpp: In function 'void upd(int, int, int, int, int, PII)':
segments.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = l + r >> 1;
      |               ~~^~~
segments.cpp: In function 'PII get(int, int, int, int, int)':
segments.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     int mid = l + r >> 1;
      |               ~~^~~
segments.cpp: In function 'int main()':
segments.cpp:102:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |                 int mid = l + r >> 1;
      |                           ~~^~~

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