Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 100005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- #define double long double
- using namespace std;
- const int inf = 1e10;
- const int minf = -1e10;
- int n, l, c;
- int vmax = 0;
- struct dat{
- int v;
- double a;
- int x, y;
- bool operator < (dat& e){
- return a < e.a;
- }
- };
- dat hs[N];
- int s[N], sum[N];
- double run_time;
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n >> l >> c;
- for(int i=1; i<=n; i++){
- cin >> hs[i].v;
- vmax = max(vmax,hs[i].v);
- }
- run_time = (double)(l*c)/(double)vmax;
- for(int i=1; i<=n; i++){
- hs[i].a = (double)(hs[i].v*l)/(double)vmax;
- hs[i].x = (int)hs[i].a;
- hs[i].y = hs[i].v*l % vmax;
- }
- sort(hs+1,hs+1+n);
- }
- int b[1000005];
- void up(int x){
- for(;x>0;x-=x&-x) b[x]++;
- }
- int get(int x){
- int res = 0;
- for(;x<=1e6;x+=x&-x) res+=b[x];
- return res;
- }
- void proc()
- {
- int res=0;
- for(int i=1; i<=n; i++) s[i] = s[i-1] + hs[i].x;
- for(int i=1; i<=n; i++) res += (i-1)*hs[i].x - s[i-1];
- for(int i=1; i<=n; i++){
- res -= get(hs[i].y+1);
- up(hs[i].y);
- }
- cout << res;
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement