fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define pb push_back
  6. #define pii pair<int, int>
  7. #define pll pair<ll, ll>
  8. #define vvi vector<vector<int>>
  9. #define vt vector
  10. #define arr array
  11. #define ALL(x) begin(x), end(x)
  12. #define rALL(x) rbegin(x), rend(x)
  13. #define SZ(x) x.size()
  14. const int MOD1=998244353;
  15. const int MOD2=1e9+7;
  16. const ll LINF=1e18;
  17. const int INF=1e9;
  18.  
  19. const int N=2e5+1;
  20. vt<ll> BIT_s(N, -LINF), BIT_g(N, -LINF);
  21. ll n, c, m, t, p, ans=0;
  22.  
  23. void upd_s(int u, ll d){
  24. for ( ; u<=n; u+=(-u&u)) BIT_s[u]=max(BIT_s[u], d);
  25. }
  26.  
  27. void upd_g(int u, ll d){
  28. for ( ; u<=n; u+=(-u&u)) BIT_g[u]=max(BIT_g[u], d);
  29. }
  30.  
  31. ll qry_s(int u, ll res=-LINF){
  32. for ( ; u; u-=(-u&u)) res=max(res, BIT_s[u]);
  33. return res;
  34. }
  35.  
  36. ll qry_g(int u, ll res=-LINF){
  37. for ( ; u; u-=(-u&u)) res=max(res, BIT_g[u]);
  38. return res;
  39. }
  40.  
  41. int main(){
  42. ios::sync_with_stdio(0);
  43. cin.tie(0); cout.tie(0);
  44.  
  45. cin>>n>>c>>m;
  46. upd_s(1, c);
  47. upd_g(n, -c);
  48.  
  49. while(m--){
  50. cin>>t>>p;
  51. // t = current market, i = previous market
  52.  
  53. // BIT_s = - c * (t - i) -> - c * t + c * i
  54. // come from market with smaller id (BIT_s) = - c * t
  55.  
  56. // BIT_g = - c * (i - t) -> - c * i + c * t
  57. // come fromt market with larger id (BIT_g) = + c * t
  58.  
  59. ll res = max(qry_s(t) - c * t, qry_g(n+1-t) + c * t) + p;
  60. ans=max(ans, res);
  61. upd_s(t, res + c * t);
  62. upd_g(n+1-t, res - c * t);
  63. }
  64. cout<<ans<<'\n';
  65.  
  66. return 0;
  67. }
Success #stdin #stdout 0.01s 6196KB
stdin
50 1000000000
15
30 60541209756
48 49238708511
1 73787345006
24 47221018887
9 20218773368
34 40025202486
14 28286410866
24 82115648680
37 62913240066
14 92020110916
24 20965327730
32 67598565422
39 79828753874
40 52778306283
40 67894622518
stdout
606214471001