fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(v) (v).begin(), (v).end()
  3. #define int long long
  4. #define rep(i, l, r) for (int i = l; i <= r; ++i)
  5. #define repd(i, r, l) for (int i = r; i >= l; --i)
  6. #define _unique(x) (x).resize(unique((x).begin(), (x).end()) - (x).begin());
  7. #define sz(v) (int)(v).size()
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define pf push_front
  12. #define mp make_pair
  13. #define eps double(1e-9)
  14. #define vii vector<int>
  15. #define pii pair<int,int>
  16. #define p2i pair<int,pii>
  17. #define endl '\n'
  18.  
  19. using namespace std;
  20.  
  21. const int N = 1e6 + 5;
  22. const int MN = 2e3 + 5;
  23. const int mod = 1e9 + 7;
  24. const int inf = 1e18 + 7;
  25. const bool Emily = false;
  26.  
  27. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  28. int rnd(int l, int r) {
  29.     return l+rng()%(r-l+1);
  30. }
  31.  
  32. bool minimize(int &a, int b) {
  33.     if (a > b) {
  34.         a = b;
  35.         return 1;
  36.     }
  37.     return 0;
  38. }
  39.  
  40. bool maximize(int &a, int b) {
  41.     if (a < b) {
  42.         a = b;
  43.         return 1;
  44.     }
  45.     return 0;
  46. }
  47.  
  48. int n, k;
  49. int a[N];
  50.  
  51. namespace sub12 {
  52.     int pre[N];
  53.     int sum(int l, int r) {
  54.         return pre[r] - pre[l - 1];
  55.     }
  56.  
  57.     int solve(void) {
  58.         rep(i, 1, n) pre[i] = pre[i - 1] + a[i];
  59.  
  60.         int res = 0;
  61.         rep(i, 1, n) rep(j, i, n) if (sum(i, j) <= k) ++res;
  62.         return res;
  63.     }
  64. }
  65.  
  66. namespace AC {
  67.     int pre[N];
  68.     int sum(int l, int r) {
  69.         return pre[r] - pre[l - 1];
  70.     }
  71.  
  72.     int solve(void) {
  73.         rep(i, 1, n) pre[i] = pre[i - 1] + a[i];
  74.  
  75.         int res = 0;
  76.         rep(i, 1, n) {
  77.             int l = i, r = n, j = -1;
  78.  
  79.             while (l <= r) {
  80.                 int mid = (l + r) >> 1;
  81.                 if (sum(i, mid) <= k) {
  82.                     l = mid + 1;
  83.                     j = mid;
  84.                 } else r = mid - 1;
  85.             }
  86.  
  87.             if (j == -1) continue;
  88.             res += (j - i + 1);
  89.         }
  90.         return res;
  91.     }
  92. }
  93.  
  94. void checker(void) {
  95.     int ntest = 100;
  96.     while (ntest-- ) {
  97.         n = rnd(100, 10000); k = rnd(1e4, 1e8);
  98.         rep(i, 1, n) a[i] = rnd(1, 1e7);
  99.  
  100.         if (sub12::solve() != AC::solve()) {
  101.             cout << "WRONG ANSWER" << endl;
  102.             return ;
  103.         }
  104.     }
  105.  
  106.     cout << "AC" << endl;
  107. }
  108.  
  109. void solve(void) {
  110.     cin >> n >> k;
  111.     rep(i, 1, n) cin >> a[i];
  112.  
  113.     if (n <= 1000) {
  114.         cout << sub12::solve();
  115.         return ;
  116.     }
  117.  
  118.     cout << AC::solve();
  119. }
  120.  
  121. signed main()
  122. {
  123.     #define task "SUBSEQ"
  124.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  125.  
  126.     freopen(task".inp", "r", stdin);
  127.     freopen(task".out", "w", stdout);
  128.  
  129.     if (Emily) {
  130.         int t; cin >> t;
  131.         while (t-- ) solve();
  132.     } else solve();
  133.  
  134.     return 0;
  135. }
  136.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/E1ZIDu
language:
C++ (gcc 8.3)
created:
2 years 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!