Submission #53394087

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using pbds =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// #define cerr if(false)cerr
#define int long long
#define pb push_back
#define F first
#define S second
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define yn(x) x ? yes : no
#define f(i, s, e) for (int i = s; i < e; i++)
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int, int>
#define vpi vector<pii>
#define all(x) x.begin(), x.end()
#define minele(x) *min_element(all(x))
#define maxele(x) *max_element(all(x))
#define endl '\n'

const int N = 2e5;
const int MOD = 1e9 + 7;
const int inf = LLONG_MAX;
const int minf = -1e14;

#ifndef ONLINE_JUDGE
#define debug(x)            \
    cerr << (#x) << " is "; \
    _print(x)
#define dbg(x...)           \
    cerr << (#x) << " is "; \
    _print(x)
#else
#define debug(x)
#define dbg(x)
#define dbg(x...)
#endif

template <typename T>
void _print(T a)
{
    cerr << a;
}
template <typename T1, typename... T2>
void _print(T1 t1, T2... t2)
{
    cerr << t1 << ", ";
    _print(t2...);
    cerr << endl;
}
template <typename T>
void print(T a)
{
    cout << a << ' ';
}
template <typename T>
void println(T a)
{
    cout << a << endl;
}
template <class T>
istream &operator>>(istream &is, vector<T> &a)
{
    for (auto &x : a)
        is >> x;
    return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a)
{
    for (const auto &x : a)
        os << x << ' ';
    return os;
}

template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
    cerr << "{";
    _print(p.F);
    cerr << ",";
    _print(p.S);
    cerr << "} ";
}
template <class T>
void _print(vector<T> v)
{
    cerr << "[ ";
    for (T i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T>
void _print(set<T> v)
{
    cerr << "[ ";
    for (T i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T>
void _print(multiset<T> v)
{
    cerr << "[ ";
    for (T i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T, class V>
void _print(map<T, V> v)
{
    cerr << "[ ";
    for (auto i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}
template <class T, class V>
void _print(unordered_map<T, V> v)
{
    cerr << "[ ";
    for (auto i : v)
    {
        _print(i);
        cerr << " ";
    }
    cerr << "]";
    cerr << endl;
}

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void init_code()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif // ONLINE_JUDGE
}

class SegmentTree
{
public:
    int n, ret;
    vi v, tree;
    void build(int low, int high, int ind)
    {
        if (low == high)
        {
            tree[ind] = v[low];
            return;
        }
        int mid = (low + high) >> 1;

        build(low, mid, 2 * ind + 1);
        build(mid + 1, high, 2 * ind + 2);

        tree[ind] = max(tree[2 * ind + 1], tree[2 * ind + 2]);
    }
    SegmentTree(vi &v)
    {
        this->v = v;
        this->n = v.size();
        tree.resize(4 * n);
        this->build(0, n - 1, 0);
    }
    void update(int low, int high, int u, int value, int ind)
    {
        if (low == high)
        {
            tree[ind] = value;
            return;
        }
        int mid = (low + high) >> 1;
        if (u <= mid)
        {
            update(low, mid, u, value, 2 * ind + 1);
        }
        else
        {
            update(mid + 1, high, u, value, 2 * ind + 2);
        }

        tree[ind] = max(tree[2 * ind + 1], tree[2 * ind + 2]);
    }
    int query(int low, int high, int l, int r, int ind)
    {
        int mid = (low + high) >> 1;
        if (low > r || high < l)
        {
            return minf;
        }
        if (low >= l && high <= r)
        {
            return tree[ind];
        }
        int left = query(low, mid, l, r, 2 * ind + 1);
        int right = query(mid + 1, high, l, r, 2 * ind + 2);

        return max(left, right);
    }
    void update(int u, int x)
    {
        update(0, n - 1, u, x, 0);
    }
    int query(int l, int r)
    {
        return query(0, n - 1, l, r, 0);
    }
};

void solve()
{
    int n, c;
    cin >> n >> c;

    vi a(n, minf), b(n);

    SegmentTree s1(a), s2(b);
    s1.update(0, -c * 1);
    s2.update(0, c * 1);
    
    int m;
    cin >> m;
    vi dp(n + 1);
    f(i, 0, m)
    {
        int y, p;
        cin >> y >> p;
        --y;
        // --y;
        // y > x
        int left = minf, right = minf;
        if(y)
            left = p - (c * (y + 1)) + s2.query(0, y - 1);
        // x > y
        if(y != n - 1)
            right = p + (c * (y + 1)) + s1.query(y + 1, n - 1);

        dp[y] = max({left, right});
        
        s1.update(y, -c * (y + 1) + dp[y]);
        s2.update(y, c * (y + 1) + dp[y]);
        debug(dp);
    }
    println(maxele(dp));
}

signed main()
{
    init_code();
    fast();
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Submission Info

Compile Error

Main.cpp:42: warning: "dbg" redefined
   42 | #define dbg(x...)
      | 
Main.cpp:41: note: this is the location of the previous definition
   41 | #define dbg(x)
      | 

Judge Result