Advertisement
Emiliatan

c260

Feb 1st, 2020
686
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.54 KB | None | 0 0
  1. /* c260             */
  2. /* AC (21ms, 2.4MB) */
  3. #pragma warning( disable : 4996 )
  4. /*
  5. #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
  6. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  7. #pragma comment(linker, "/stack:200000000")
  8. #pragma GCC optimize("O3")
  9. */
  10. //#include <bits/stdc++.h>
  11. #include <cstdio>
  12. #include <cstring>
  13. #include <climits>
  14. #include <cmath>
  15. #include <algorithm>
  16. #include <tuple>
  17. #define ios_jazz ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  18. #define FOR(i, l, r) for (int i = (l); i < (r); ++i)
  19. #define FORR(i, r, l) for (int i =(r); i >= (l); --i)
  20. #define P(STR) puts(#STR)
  21.  
  22. using namespace std;
  23.  
  24. constexpr int Dir4[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
  25. constexpr int Dir8[8][2] = { {-1, -1}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 1} };
  26. constexpr double EPS = 1e-8;
  27. const double PI = acos(-1);
  28.  
  29. using int16 = short;
  30. using uint16 = unsigned short;
  31. using uint = unsigned int;
  32. using int64 = long long;
  33. using uint64 = unsigned long long;
  34. using pii = pair<int, int>;
  35.  
  36. auto Equal = [](double a, double b) { return fabs(a - b) < EPS; };
  37.  
  38. /* mods */
  39.  
  40. /* main code */
  41. #include <vector>
  42.  
  43. constexpr int MAXN = 1e5;
  44. int n;
  45. int64 a, b;
  46. int64 arr[2][MAXN + 1]{};
  47. int64 tmp[MAXN + 10];
  48.  
  49. enum { A, B };
  50. int64 sort(int idx, int l = 0, int r = n)
  51. {
  52.     if (r == l)
  53.     {
  54.         if (idx == A && arr[idx][l] == INT64_MAX) return 0;
  55.         else if (idx == B && arr[idx][l] == INT64_MIN) return 0;
  56.         if (idx == A)
  57.             return (arr[idx][l] >= 0);
  58.         else
  59.             return (arr[idx][r] <= 0);
  60.     }
  61.  
  62.     int mid = (l + r) / 2;
  63.  
  64.     int64 Lval = sort(idx, l, mid);
  65.     int64 Rval = sort(idx, mid + 1, r);
  66.     int64 Nowval = 0;
  67.  
  68.     int64 lptr = l;
  69.     int64 rptr = mid + 1LL;
  70.     int64 N = 0;
  71.  
  72.     for (; lptr <= mid; ++lptr)
  73.     {
  74.         while (rptr <= r && arr[idx][lptr] >= arr[idx][rptr])
  75.         {
  76.             tmp[N++] = arr[idx][rptr++];
  77.             Nowval += ((int64)mid - lptr + 1);
  78.         }
  79.  
  80.         tmp[N++] = arr[idx][lptr];
  81.     }
  82.  
  83.     while (lptr <= mid)
  84.         tmp[N++] = arr[idx][lptr++];
  85.     while (rptr <= r)
  86.         tmp[N++] = arr[idx][rptr++];
  87.  
  88.     for (int i = 0; i < N; ++i)
  89.         arr[idx][l + i] = tmp[i];
  90.  
  91.     return Nowval + Lval + Rval;
  92. }
  93.  
  94. int main()
  95. {
  96.     scanf("%d %lld %lld", &n, &a, &b);
  97.  
  98.     FOR(i, 1, n + 1)
  99.         scanf("%lld", &arr[0][i]);
  100.  
  101.     FOR(i, 1, n + 1)
  102.     {
  103.         arr[1][i] = arr[0][i] - b;
  104.         arr[1][i] += arr[1][i - 1];
  105.         arr[0][i] -= a;
  106.         arr[0][i] += arr[0][i - 1];
  107.     }
  108.  
  109.     arr[A][0] = INT64_MAX;
  110.     arr[B][0] = INT64_MIN;
  111.  
  112.     reverse(arr[A], arr[A] + n + 1);
  113.  
  114.     printf("%lld\n", sort(A) + sort(B) - n * (n + 1LL) / 2);
  115.  
  116.     return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement