Submission #86754

#	Time	Username	Problem	Language	Result	Execution time	Memory
86754		karma	Divide and conquer (IZhO14_divide)	C++11	100 / 100	72 ms	5600 KiB

divide

#include<bits/stdc++.h>
#define For(i, a, b)  for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Task          "test"
#define ld            long double
#define ll            long long
#define X             first
#define Y             second
#define pb            push_back
//#define Karma

using namespace std;

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

typedef pair<int, int> pii;
typedef pair<ll, int> plli;
const int N = 2e5 + 7;

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

void Update(int x, int val)
{
     if(x == 0) return;
     while(x <= Maxv)
     {
         t[x] = min(t[x], val);
         x += (x & -x);
     }
}

int Query(int x)
{
    if(x == 0) return Maxv;
    int res = Maxv;
    while(x > 0)
    {
        res = min(res, t[x]);
        x -= (x & -x);
    }
    return res;
}

void Enter()
{
     Cin(n);
     Maxv = 2 * n + 2;
     fill_n(t, Maxv + 2, Maxv);
     For(i, 1, n)
     {
         Cin(x[i]), Cin(g[i]), Cin(r[i]);
         g[i] += g[i - 1], r[i] += r[i - 1];
         v.pb(r[i - 1] - x[i]);
         v.pb(r[i] - x[i]);
     }
     sort(v.begin(), v.end());
     v.erase(unique(v.begin(), v.end()), v.end());
}

void Solve()
{
     For(i, 1, n)
     {
         res = max(res, g[i] - g[i - 1]);
         int p = lower_bound(v.begin(), v.end(), r[i] - x[i]) - v.begin() + 1;
         int j = Query(p);
         if(j < Maxv) res = max(res, g[i] - g[j - 1]);
         p = lower_bound(v.begin(), v.end(), r[i - 1] - x[i]) - v.begin() + 1;
         Update(p, i);
     }
     cout << 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

    Enter();
    Solve();

    return 0;

}

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