Submission #775799

#	Time	Username	Problem	Language	Result	Execution time	Memory
775799		anha3k25cvp	Divide and conquer (IZhO14_divide)	C++14	100 / 100	41 ms	8792 KiB

divide

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const ll inf = 7 + 1e18;

struct Fenwick {
    int n;
    vector <ll> tree;
    Fenwick (int _n = 0) : n(_n) {
        tree.assign(n + 1, inf);
    }
    void update(int x, ll val) {
        for (int i = x; i <= n; i += i & -i)
            tree[i] = min(tree[i], val);
    }
    ll get(int x) {
        ll ans = inf;
        for (int i = x; i > 0; i -= i & -i)
            ans = min(ans, tree[i]);
        return ans;
    }
};

vector <ll> x, g, d, c;

int main() {
#define TASKNAME ""
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    int n;
    cin >> n;
    x.assign(n + 1, 0);
    g.assign(n + 1, 0);
    d.assign(n + 1, 0);
    ll ans = 0;
    for (int i = 1; i <= n; i ++) {
        cin >> x[i] >> g[i] >> d[i];
        ans = max(ans, g[i]);
        g[i] += g[i - 1];
        d[i] += d[i - 1];
        c.push_back(d[i] - x[i]);
        c.push_back(d[i - 1] - x[i]);
    }
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    Fenwick f(c.size());
    for (int i = 1; i <= n; i ++) {
        int val = lower_bound(c.begin(), c.end(), d[i] - x[i]) - c.begin() + 1;
        ans = max(ans, g[i] - f.get(val));
        val = lower_bound(c.begin(), c.end(), d[i - 1] - x[i]) - c.begin() + 1;
        f.update(val, g[i - 1]);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:39:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:40:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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