fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pp push_back
  5. #define endl '\n'
  6. #define all(x) x.begin(),x.end()
  7. #define ld long double
  8. #define PI acos(-1)
  9. #define ones(x) __builtin_popcountll(x)
  10. //#define int ll
  11.  
  12. using namespace std;
  13.  
  14. void Drakon() {
  15.     ios_base::sync_with_stdio(false);
  16.     cin.tie(nullptr);
  17.     cout.tie(nullptr);
  18. #ifdef Clion
  19.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  20. #endif
  21. }
  22.  
  23. unsigned long long inf = 1e10;
  24. const double EPS = 1e-6;
  25. const int MOD = 1000000007, N = 200005, LOG = 25;
  26.  
  27. ll mul(const ll &a, const ll &b) {
  28.     return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
  29. }
  30.  
  31. ll add(const ll &a, const ll &b) {
  32.     return (a + b + 2 * MOD) % MOD;
  33. }
  34.  
  35. ll pw(ll x, ll y) {
  36.     ll ret = 1;
  37.     while (y > 0) {
  38.         if (y % 2 == 0) {
  39.             x = mul(x, x);
  40.             y = y / 2;
  41.         } else {
  42.             ret = mul(ret, x);
  43.             y = y - 1;
  44.         }
  45.     }
  46.     return ret;
  47. }
  48.  
  49. #include <ext/pb_ds/assoc_container.hpp>
  50. #include <ext/pb_ds/tree_policy.hpp>
  51.  
  52. using namespace __gnu_pbds;
  53. template<typename T>
  54. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  55.  
  56. ll sumNeg = 0, e;
  57. multiset<int> neg, pos;
  58. ordered_set<pair<ll, int>> pres;
  59. vector<ll> pre;
  60.  
  61. void add(int a, int b, int i) {
  62.     if((b - a) >= 0) {
  63.         pos.insert(a);
  64.     }
  65.     else {
  66.         sumNeg += b - a;
  67.         neg.insert(b);
  68.     }
  69.     pres.insert({pre[i], i});
  70. }
  71.  
  72. void rem(int a, int b, int i) {
  73.     if((b - a) >= 0) {
  74.         pos.erase(pos.find(a));
  75.     }
  76.     else {
  77.         sumNeg -= b - a;
  78.         neg.erase(neg.find(b));
  79.     }
  80.     pres.erase({pre[i], i});
  81. }
  82.  
  83. bool check() {
  84.     if(!pos.empty()) {
  85.         if(e + sumNeg < *pos.rbegin()) return false;
  86.     }
  87.     if(!neg.empty()) {
  88.         if(e + sumNeg - *neg.rbegin() < 0) return false;
  89.     }
  90.     return true;
  91. }
  92.  
  93. void solve() {
  94.     int n;
  95.     cin >> n >> e;
  96.     vector<int> a(n), b(n);
  97.     for (int i = 0; i < n; ++i) {
  98.         cin >> a[i];
  99.     }
  100.     for (int i = 0; i < n; ++i) {
  101.         cin >> b[i];
  102.     }
  103.  
  104.     pre.resize(n);
  105.     for (int i = 0; i < n; ++i) {
  106.         pre[i] = (i ? pre[i - 1] : 0) + b[i] - a[i];
  107.     }
  108.  
  109.     int r = 0;
  110.     ll ans = 0;
  111.  
  112.     for (int i = 0; i < n; ++i) {
  113.         r = max(r, i);
  114.         while (r < n) {
  115.             add(a[r], b[r], r);
  116.             if(check()) r ++;
  117.             else {
  118.                 rem(a[r], b[r], r);
  119.                 break;
  120.             }
  121.         }
  122.         ans += r - i - pres.order_of_key({i ? pre[i - 1] : 0, -1});
  123.         if(r > i)
  124.             rem(a[i], b[i], i);
  125.     }
  126.     cout << ans << endl;
  127. }
  128.  
  129. signed main() {
  130.     Drakon();
  131.     int t = 1;
  132.     //cin >> t;
  133.     while (t--) {
  134.         solve();
  135.     }
  136. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/QSFCrw
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!