Submission #1032208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032208		MongHwa	Divide and conquer (IZhO14_divide)	C++17	100 / 100	42 ms	8148 KiB

divide

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

#define ll long long

ll x[100005], g[100005], d[100005];
vector<pair<ll, int>> v;

void init(vector<int>& tree, int node, int start, int end)
{
    if(start == end)
        tree[node] = v[start].second;
    else
    {
        init(tree, node*2, start, (start+end)/2);
        init(tree, node*2+1, (start+end)/2+1, end);
        tree[node] = max(tree[node*2], tree[node*2+1]);
    }
}

int query(vector<int>& tree, int node, int start, int end, int left, int right)
{
    if(right < start || left > end)
        return 0;
    if(left <= start && end <= right)
        return tree[node];
    
    int l = query(tree, node*2, start, (start+end)/2, left, right);
    int r = query(tree, node*2+1, (start+end)/2+1, end, left, right);
    return max(l, r);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        cin >> x[i] >> g[i] >> d[i];
    
    for(int i = 1; i <= n; i++)
    {
        g[i] += g[i-1];
        d[i] += d[i-1];

        v.push_back({x[i]-d[i], i});
    }

    sort(v.begin(), v.end());

    int h = (int)ceil(log2(n));
    int tree_size = (1<<(h+1));
    vector<int> segtree(tree_size);

    init(segtree, 1, 0, n-1);

    ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        int pos = upper_bound(v.begin(), v.end(), make_pair(x[i]-d[i-1], n)) - v.begin();
        pos--;

        int j = query(segtree, 1, 0, n-1, 0, pos);
        if(j >= i)
            ans = max(ans, g[j]-g[i-1]);
    }

    cout << ans << '\n';
}

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