oj.uz

Submission #171724

# Submission time Handle Problem Language Result Execution time Memory
171724 2019-12-30T07:55:04 Z davitmarg Divide and conquer (IZhO14_divide) C++17
100 / 100
 495 ms 158856 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] = 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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 1264 KB Output is correct
4 Correct 5 ms 1524 KB Output is correct
5 Correct 6 ms 1776 KB Output is correct
6 Correct 9 ms 2668 KB Output is correct
7 Correct 6 ms 1644 KB Output is correct
8 Correct 6 ms 1776 KB Output is correct
9 Correct 7 ms 1268 KB Output is correct
10 Correct 8 ms 1552 KB Output is correct
11 Correct 19 ms 5092 KB Output is correct
12 Correct 24 ms 8040 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2540 KB Output is correct
2 Correct 28 ms 5860 KB Output is correct
3 Correct 50 ms 16932 KB Output is correct
4 Correct 224 ms 75424 KB Output is correct
5 Correct 239 ms 75744 KB Output is correct
6 Correct 495 ms 158856 KB Output is correct
7 Correct 412 ms 124816 KB Output is correct
8 Correct 419 ms 125080 KB Output is correct
9 Correct 304 ms 69944 KB Output is correct
10 Correct 242 ms 36664 KB Output is correct
11 Correct 323 ms 76700 KB Output is correct
12 Correct 396 ms 125532 KB Output is correct