oj.uz

Submission #171721

# Submission time Handle Problem Language Result Execution time Memory
171721 2019-12-30T07:39:33 Z davitmarg Divide and conquer (IZhO14_divide) C++17
0 / 100
 15 ms 2664 KB 
/*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] = max(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 + x[i] - d[i - 1], pr[i - 1]);
        LL res = -get(0, 0, mod * mod, mod * n + x[i] - d[i], mod * mod) + pr[i];
        //cout << res << endl;
        ans = max(ans, res);
    }
    cout << ans << endl;
    return 0;
}

/*


*/

Compilation message

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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2664 KB Output isn't correct
2 Halted 0 ms 0 KB -