Submission #745159

#	Time	Username	Problem	Language	Result	Execution time	Memory
745159		Desh03	Divide and conquer (IZhO14_divide)	C++17	100 / 100	113 ms	10696 KiB

divide

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct segtree {
    vector<int> st;
    int sz;
    segtree(vector<int> a) {
        sz = a.size();
        while (sz & sz - 1) ++sz;
        st.resize(sz << 1, 1e18);
        for (int i = 0; i < a.size(); i++) st[i + sz] = a[i];
        for (int i = sz - 1; i; --i) pull(i);
    }
    void pull(int v) {
        st[v] = min(st[v << 1], st[v << 1 | 1]);
    }
    int findfirst(int v, int l, int r, int ql, int qr, int x) {
        if (l > qr || r < ql) return -1;
        if (l >= ql && r <= qr) {
            if (st[v] > x) return -1;
            while (l < r) {
                int m = l + r >> 1;
                if (st[v << 1] <= x) v <<= 1, r = m;
                else v <<= 1, v |= 1, l = m + 1;
            }
            return l;
        }
        int m = l + r >> 1;
        int s = findfirst(v << 1, l, m, ql, qr, x);
        if (s != -1) return s;
        return findfirst(v << 1 | 1, m + 1, r, ql, qr, x);
    }
    int findfirst(int l, int r, int x) {
        return findfirst(1, 0, sz - 1, l, r, x);
    }
};

signed main() {
    int n, ans = -1e18;
    cin >> n;
    vector<int> x(n), g(n), d(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> g[i] >> d[i];
    vector<int> pre1(n + 1), pre2(n + 1), f(n + 1);
    for (int i = 0; i < n; i++) pre1[i + 1] = pre1[i] + g[i], pre2[i + 1] = pre2[i] + d[i];
    f[0] = 1e18;
    for (int i = 1; i <= n; i++) f[i] = pre2[i - 1] - x[i - 1];
    segtree st(f);
    for (int i = 1; i <= n; i++) {
        int k = st.findfirst(0, i, pre2[i] - x[i - 1]);
        if (k == -1) continue;
        ans = max(ans, pre1[i] - pre1[k - 1]);
    }
    cout << ans << '\n';
}

Compilation message (stderr)

divide.cpp: In constructor 'segtree::segtree(std::vector<long long int>)':
divide.cpp:10:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   10 |         while (sz & sz - 1) ++sz;
      |                     ~~~^~~
divide.cpp:12:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for (int i = 0; i < a.size(); i++) st[i + sz] = a[i];
      |                         ~~^~~~~~~~~~
divide.cpp: In member function 'long long int segtree::findfirst(long long int, long long int, long long int, long long int, long long int, long long int)':
divide.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |                 int m = l + r >> 1;
      |                         ~~^~~
divide.cpp:29:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int m = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52