Advertisement
Naxocist

rope

Apr 29th, 2023
581
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using pi = pair<ll, ll>;
  5. ll f(ll l, ll r) {
  6.     ll n = r-l+1;
  7.     return n*(n+1)/2;
  8. }
  9. int main() {
  10.     cin.tie(nullptr)->sync_with_stdio(false);
  11.     int n, p; cin >> n >> p;
  12.     ll x, y, z; cin >> x >> y >> z;
  13.     multiset<ll> ms;
  14.     vector<ll> cnt(5e5+3, 0), A(n), B(n);
  15.     for(auto &x : A) cin >> x;
  16.     for(auto &x : B) cin >> x;
  17.     vector<pi> w;
  18.     ll l, r, pt, res, ed = -1; res = l = r = pt = 0;
  19.     for(; l<n; ++l) {
  20.         for(;r<n;r++){
  21.             ll a = A[r], b = B[r];
  22.             if(pt + a > x) break ;
  23.             if(y != -1 and ms.size()) {
  24.                 ll mx = *(--ms.end()), mn = *(ms.begin());
  25.                 if(a > mx and a - mn > y) break ;
  26.                 else if(a < mn and mx - a > y) break ;
  27.             }
  28.             if(z != -1 and cnt[b] + 1 > z) break ;
  29.             pt += a;
  30.             if(y != -1) ms.insert(a);
  31.             if(z != -1) cnt[b] ++;
  32.         }
  33.         pt-=(ll)A[l];
  34.         if(y != -1) ms.erase(ms.find(A[l]));
  35.         if(z != -1) cnt[B[l]] -- ;
  36.        
  37.         res += f(l, r-1);
  38.         if(l <= ed) res -= f(l, ed);
  39.         ed = r-1;
  40.     }
  41.  
  42.     cout << res;
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement