Advertisement
momo2345

petya and array

Sep 25th, 2020
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. using namespace __gnu_pbds;
  6. typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
  7. #define suni ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  8. #define endl "\n"
  9. #define mn int main()
  10. #define frac() cout.unsetf(ios::floatfield);cout.precision(6);cout.setf(ios::fixed,ios::floatfield);
  11. const ll mx=2e5+123;
  12. ll sum[mx];
  13. mn
  14. {
  15.     suni;
  16.     ll n,t; cin>>n>>t;
  17.     for(int i=1;i<=n;i++){
  18.         ll a; cin>>a;
  19.         sum[i]=a+sum[i-1];
  20.         }
  21.     ordered_set p;
  22.     map<ll,ll>cnt;
  23.     p.insert(0);
  24.     cnt[0]++;
  25.     ll ans=0;
  26.     for(int i=1;i<=n;i++){
  27.       ll d=sum[i]-t;
  28.       ans+=(i-p.order_of_key(d)-cnt[d]);
  29.       p.insert(sum[i]);
  30.       cnt[sum[i]]++;
  31.     }
  32.     cout<<ans<<endl;
  33.     }
  34.  
  35.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement