fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define itachi ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define all(v) v.begin(),v.end()
  8. #define maxn 200005
  9. using namespace std;
  10.  
  11. int n,m;
  12. ll aa[maxn], bb[maxn];
  13. int vt[maxn], pos[maxn];
  14. ll A[maxn], B[maxn], prefA[maxn], prefB[maxn];
  15. long double rat[maxn];
  16. ll prefCost[maxn];
  17.  
  18. int main(){
  19.     itachi
  20.     if(!(cin >> n >> m)) return 0;
  21.     for(int i=1;i<=n;i++) cin >> aa[i];
  22.     for(int i=1;i<=n;i++) cin >> bb[i];
  23.  
  24.     for(int i=1;i<=n;i++) vt[i]=i;
  25.     sort(vt+1, vt+n+1, [&](int i,int j){
  26.         return (ll)bb[i]*aa[j] < (ll)bb[j]*aa[i];
  27.     });
  28.  
  29.     for(int i=1;i<=n;i++){
  30.         A[i] = aa[vt[i]];
  31.         B[i] = bb[vt[i]];
  32.         pos[vt[i]] = i;
  33.         prefA[i] = prefA[i-1] + A[i];
  34.         prefB[i] = prefB[i-1] + B[i];
  35.         rat[i] = (long double)B[i]/A[i];
  36.         prefCost[i] = prefCost[i-1] + A[i]*prefB[i];
  37.     }
  38.     ll totalCost = prefCost[n];
  39.  
  40.     while(m--){
  41.         int x,y; cin >> x >> y;
  42.         int px = pos[x], py = pos[y];
  43.         if(px < py){
  44.             cout << totalCost << "\n";
  45.             continue;
  46.         }
  47.         int L = py, R = px;
  48.         long double rblock = (long double)(bb[x]+bb[y]) / (long double)(aa[x]+aa[y]);
  49.         int lo = L, hi = R-1, idx = L-1;
  50.         while(lo <= hi){    
  51.             int mid = (lo+hi)/2;
  52.             if(rat[mid] <= rblock) lo = mid+1;
  53.             else hi = mid-1;
  54.         }
  55.         idx = hi;
  56.         int k = idx;
  57.         ll ans = 0;
  58.  
  59.         if(k == L-1){
  60.             ans += prefCost[L-1];
  61.         } else {
  62.             ans += prefCost[L-1];
  63.             ans += (prefCost[k] - prefCost[L]);
  64.             ll sumA_mid = prefA[k] - prefA[L];
  65.             ans -= B[L] * sumA_mid;
  66.         }
  67.  
  68.         ll TB = prefB[k] - ((k>=L)?B[L]:0);
  69.  
  70.         ll Au = A[R], Bu = B[R];
  71.         ll Av = A[L], Bv = B[L];
  72.  
  73.         ans += (TB + Bu) * Au;
  74.         ans += (TB + Bu + Bv) * Av;
  75.  
  76.         ll base_after = prefCost[n] - prefCost[k];
  77.         if(k == L-1) base_after -= Av * prefB[L];
  78.         base_after -= Au * prefB[R];
  79.  
  80.         ll sumA_segment = 0;
  81.         if(R-1 >= k+1){
  82.             sumA_segment = prefA[R-1] - prefA[k];
  83.             if(k == L-1) sumA_segment -= Av;
  84.         }
  85.  
  86.         base_after += Bu * sumA_segment;
  87.         ans += base_after;
  88.  
  89.         cout << ans << "\n";
  90.     }
  91.  
  92.     return 0;
  93. }
  94.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fJ1D6G
language:
C++14 (gcc 8.3)
created:
2 days 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!