Submission #86813

#	Time	Username	Problem	Language	Result	Execution time	Memory
86813		karma	Divide and conquer (IZhO14_divide)	C++11	100 / 100	59 ms	4500 KiB

divide

#include<bits/stdc++.h>
#define ll            long long
#define pb            push_back

using namespace std;

template <typename T> inline void Cin(T &x)
{
    register char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar());
    for (x = 0; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

ll res;
int n, Maxv;
vector<ll> v, x, g, r;
vector<int> t;

inline void Minimize(int& x, int y) {if(x > y) x = y;}
inline void Update(int x, int val)
{
    while(x <= Maxv)
    {
        Minimize(t[x], val);
        x += (x & -x);
    }
}
inline int Query(int x)
{
    int res = Maxv;
    while(x > 0)
    {
        Minimize(res, t[x]);
        x -= (x & -x);
    }
    return res;
}

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

    Cin(n);
    Maxv = n + 3;
    t.resize(Maxv + 1, Maxv);
    x.resize(n + 1), g.resize(n + 1), r.resize(n + 1);
    g[0] = r[0] = x[0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        Cin(x[i]), Cin(g[i]), Cin(r[i]);
        res = max(res, g[i]);
        g[i] += g[i - 1], r[i] += r[i - 1];
        v.pb(r[i - 1] - x[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    v.pb(v.back() + 1);
    for(int i = 1; i <= n; ++i)
    {
        int j = Query(upper_bound(v.begin(), v.end(), r[i] - x[i]) - v.begin());
        if(j < Maxv) res = max(res, g[i] - g[j - 1]);
        Update(lower_bound(v.begin(), v.end(), r[i - 1] - x[i]) - v.begin() + 1, i);
    }
    cout << res;
}

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