Submission #171724

#	Time	Username	Problem	Language	Result	Execution time	Memory
171724		davitmarg	Divide and conquer (IZhO14_divide)	C++17	100 / 100	495 ms	158856 KiB

divide

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 300005;

LL n;
LL x[N], pr[N], d[N], ans;
vector<LL> t;
vector<int> L, R;

void addNode(LL val = 0)
{
    t.PB(val);
    L.PB(-1);
    R.PB(-1);
}

void upd(int v, LL l, LL r, LL pos, LL val)
{
    //cout << l << " : " << r << endl;
    if (l == r)
    {
        t[v] = min(t[v], val);
        return;
    }
    if (L[v] == -1)
    {
        addNode(mod * mod);
        L[v] = t.size() - 1;
        addNode(mod * mod);
        R[v] = t.size() - 1;
    }
    LL m = (l + r) / 2;
    if (pos <= m)
        upd(L[v], l, m, pos, val);
    else
        upd(R[v], m + 1, r, pos, val);
    t[v] = min(t[L[v]], t[R[v]]);
}

LL get(int v, LL l, LL r, LL i, LL j)
{
    if (i > j)
        return mod * mod;
    if (l == i && r == j)
        return t[v];
    LL m = (l + r) / 2;
    if (L[v] == -1)
    {
        addNode(mod * mod);
        L[v] = t.size() - 1;
        addNode(mod * mod);
        R[v] = t.size() - 1;
    }
    return min(
        get(L[v], l, m, i, min(m, j)),
        get(R[v], m + 1, r, max(m + 1, i), j));
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld%lld", x + i, pr + i, d + i);
        pr[i] += pr[i - 1];
        d[i] += d[i - 1];
    }
    addNode(mod * mod);

    for (int i = 1; i <= n; i++)
    {
        upd(0, 0, mod * mod, mod * n + d[i - 1] - x[i], pr[i - 1]);
        //cout << get(0, 0, mod * mod, 0, mod * n + d[i - 1] - x[i]) << endl;
        LL res = -get(0, 0, mod * mod, 0, mod * n + d[i] - x[i]) + pr[i];
        ans = max(ans, res);
    }
    cout << ans << endl;
    return 0;
}

/*

1
0 5 1

4
0 5 1
1 7 2
5 4 1
8 15 1

*/

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld", x + i, pr + i, d + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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