Submission #53340353

---

Source Code Expand

// #pragma GCC optimize("Ofast,O3,unroll-loops")
// #pragma GCC target("avx,avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
#define bit(x, i) (((x) >> (i)) & 1)
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 2e5 + 50;

template <typename T, T neutral_element, class F = function<T(const T&, const T&)>>
struct SegmentTree{
    int n = 0;
    vector<T> tree;
    F func;

    SegmentTree(){};
    SegmentTree(int _n, const F& f){
        n = _n;
        func = f;
        tree.assign(n * 4 + 5, neutral_element);
    }

    inline void build(int v, int tl, int tr, const vector<T> &a){
        if (tl == tr){
            tree[v] = a[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm, a);
        build(v << 1 | 1, tm + 1, tr, a);
        tree[v] = func(tree[v << 1], tree[v << 1 | 1]);
    }

    inline void init(const vector<T> &a, const F& f){
        n = (int)a.size();
        func = f;
        tree.assign(n * 4 + 5, neutral_element);
        build(1, 0, n - 1, a);
    }

    inline void update(int v, int tl, int tr, int pos, T val){
        if (tl == tr){
            tree[v] = max(tree[v], val);
            return;
        }
        int tm = (tl + tr) >> 1;
        if (pos <= tm){
            update(v << 1, tl, tm, pos, val);
        } else {
            update(v << 1 | 1, tm + 1, tr, pos, val);
        }
        tree[v] = func(tree[v << 1], tree[v << 1 | 1]);
    }

    inline void update(int pos, T val){
        update(1, 0, n - 1, pos, val);
    }

    inline T get(int v, int tl, int tr, int l, int r){
        if (l <= tl && tr <= r) return tree[v];
        if (tl > r || tr < l) return neutral_element;
        int tm = (tl + tr) >> 1;
        return func(get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
    }

    inline T get(int l, int r){
        return get(1, 0, n - 1, l, r);
    }

};

/*
vector<int> a = {1, 2, 5, 3, 4};
SegmentTree<int, INT_MIN> st(a, [&](int i, int j){ return max(i, j); });

SegmentTree<int, 0> st(100, [&](int i, int j){ return i + j; });
*/

void solve() {
    int n, m; long long C;
    cin >> n >> C >> m;

    const long long INF = 4e18;

    SegmentTree<long long, -INF> st1(n, [&](long long x, long long y){return max(x, y);});
    SegmentTree<long long, -INF> st2(n, [&](long long x, long long y){return max(x, y);});

    st1.update(0, 0);
    st2.update(0, 0);

    long long ans = 0;

    while (m--) {
        int t; long long p;
        cin >> t >> p;
        --t;

        long long val1 = p - C * t + st1.get(0, t);
        long long val2 = p + C * t + st2.get(t, n - 1);
        long long val = max(val1, val2);

        st1.update(t, val + C * t);
        st2.update(t, val - C * t);

        ans = max(ans, val);
    }

    cout << ans << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
    // cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:125:13: warning: unused variable ‘startTime’ [-Wunused-variable]
  125 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Judge Result