Advertisement
MinhNGUYEN2k4

Untitled

Sep 13th, 2021
868
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 100005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20. #define double long double
  21.  
  22. using namespace std;
  23.  
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, l, c;
  28. int vmax = 0;
  29. struct dat{
  30.     int v;
  31.     double a;
  32.     int x, y;
  33.     bool operator < (dat& e){
  34.         return a < e.a;
  35.     }
  36. };
  37. dat hs[N];
  38. int s[N], sum[N];
  39. double run_time;
  40.  
  41. void readfile()
  42. {
  43.     ios_base::sync_with_stdio(false);
  44.     cin.tie(0);cout.tie(0);
  45.     if (fopen(Task".inp","r"))
  46.     {
  47.         freopen(Task".inp","r",stdin);
  48.         //freopen(Task".out","w",stdout);
  49.     }
  50.     cin >> n >> l >> c;
  51.     for(int i=1; i<=n; i++){
  52.         cin >> hs[i].v;
  53.         vmax = max(vmax,hs[i].v);
  54.     }
  55.     run_time = (double)(l*c)/(double)vmax;
  56.     for(int i=1; i<=n; i++){
  57.         hs[i].a = (double)(hs[i].v*l)/(double)vmax;
  58.         hs[i].x = (int)hs[i].a;
  59.         hs[i].y = hs[i].v*l % vmax;
  60.     }
  61.     sort(hs+1,hs+1+n);
  62. }
  63.  
  64. int b[1000005];
  65.  
  66. void up(int x){
  67.     for(;x>0;x-=x&-x) b[x]++;
  68. }
  69.  
  70. int get(int x){
  71.     int res = 0;
  72.     for(;x<=1e6;x+=x&-x) res+=b[x];
  73.     return res;
  74. }
  75.  
  76. void proc()
  77. {
  78.     int res=0;
  79.     for(int i=1; i<=n; i++) s[i] = s[i-1] + hs[i].x;
  80.     for(int i=1; i<=n; i++) res += (i-1)*hs[i].x - s[i-1];
  81.     for(int i=1; i<=n; i++){
  82.         res -= get(hs[i].y+1);
  83.         up(hs[i].y);
  84.     }
  85.     cout << res;
  86. }
  87.  
  88. signed main()
  89. {
  90.     readfile();
  91.     proc();
  92.     return 0;
  93. }
  94.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement