Submission #86771

#	Time	Username	Problem	Language	Result	Execution time	Memory
86771		karma	Divide and conquer (IZhO14_divide)	C++11	100 / 100	48 ms	4212 KiB

divide

#include<bits/stdc++.h>
#define ll            long long
#define pb            push_back
//#define Karma
 
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';
}
 
const int N = 1e5 + 7;
 
ll x[N], g[N], r[N], res;
int t[N], n, Maxv;
vector<ll> v;
 
inline void Minimize(int& x, int y) {if(x < y) x = y;}
inline void Update(int x, int val)
{
    while(x <= Maxv)
    {
        t[x] = min(t[x], val);
        x += (x & -x);
    }
}
inline int Query(int x)
{
    int res = Maxv;
    while(x > 0)
    {
        res = min(res, t[x]);
        x -= (x & -x);
    }
    return res;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#ifdef Karma
    freopen(Task".inp", "r", stdin);
    freopen(Task".out", "w", stdout);
#endif // Karma
 
    Cin(n);
    Maxv = n + 5;
    fill_n(t, Maxv + 2, Maxv);
    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;
 
    return 0;
 
}

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