fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using i128 = __int128_t;
  5.  
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.     int n, m;
  10.     if(!(cin >> n >> m)) return 0;
  11.     vector<ll> aa(n+1), bb(n+1);
  12.     for(int i=1;i<=n;i++) cin >> aa[i];
  13.     for(int i=1;i<=n;i++) cin >> bb[i];
  14.  
  15.     vector<int> vt(n+1);
  16.     for(int i=1;i<=n;i++) vt[i]=i;
  17.     auto cmp = [&](int i, int j){
  18.         return (i128)bb[i]*aa[j] < (i128)bb[j]*aa[i];
  19.     };
  20.     stable_sort(vt.begin()+1, vt.end(), cmp);
  21.  
  22.     vector<ll> A(n+1), B(n+1);
  23.     for(int i=1;i<=n;i++){
  24.         A[i] = aa[vt[i]];
  25.         B[i] = bb[vt[i]];
  26.     }
  27.     vector<int> pos(n+1);
  28.     for(int i=1;i<=n;i++) pos[vt[i]] = i;
  29.  
  30.     vector<ll> prefA(n+1,0), prefB(n+1,0);
  31.     vector<long double> rat(n+1,0.0L);
  32.     vector<i128> prefCost128(n+1,0);
  33.     for(int i=1;i<=n;i++){
  34.         prefA[i] = prefA[i-1] + A[i];
  35.         prefB[i] = prefB[i-1] + B[i];
  36.         rat[i] = (long double)B[i] / (long double)A[i];
  37.         prefCost128[i] = prefCost128[i-1] + (i128)A[i] * (i128)prefB[i];
  38.     }
  39.     i128 total_full_128 = prefCost128[n];
  40.  
  41.     auto print_i128 = [&](i128 x){
  42.         if(x==0){ cout << 0 << '\n'; return;}
  43.         string s;
  44.         while(x>0){
  45.             int d = (int)(x % 10);
  46.             s.push_back(char('0'+d));
  47.             x /= 10;
  48.         }
  49.         reverse(s.begin(), s.end());
  50.         cout << s << '\n';
  51.     };
  52.  
  53.     while(m--){
  54.         int x,y; cin >> x >> y;
  55.         int px = pos[x], py = pos[y];
  56.         if(px < py){
  57.             print_i128(total_full_128);
  58.             continue;
  59.         }
  60.         int L = py, R = px; 
  61.         long double rblock = (long double)(bb[x] + bb[y]) / (long double)(aa[x] + aa[y]);
  62.  
  63.         int lo = L, hi = R-1;
  64.         int idx = L-1;
  65.         if(lo <= hi){
  66.             auto it = upper_bound(rat.begin()+lo, rat.begin()+hi+1, rblock);
  67.             idx = int(it - rat.begin()) - 1;
  68.         } else {
  69.             idx = L-1;
  70.         }
  71.         int k = idx; 
  72.         i128 ans = 0;
  73.  
  74.         if(k == L-1){
  75.             ans += prefCost128[L-1];
  76.         } else {
  77.             ans += prefCost128[L-1];
  78.             ans += (prefCost128[k] - prefCost128[L]);
  79.             ll sumA_mid = prefA[k] - prefA[L];
  80.             ans -= (i128)B[L] * (i128)sumA_mid;
  81.         }
  82.  
  83.         ll TB = prefB[k] - ( (k>=L) ? B[L] : 0 );
  84.  
  85.         ll Au = A[R], Bu = B[R]; 
  86.         ll Av = A[L], Bv = B[L]; 
  87.  
  88.         ans += (i128)(TB + Bu) * (i128)Au;
  89.         ans += (i128)(TB + Bu + Bv) * (i128)Av;
  90.  
  91.         i128 base_after = prefCost128[n] - prefCost128[k];
  92.         if(k == L-1){
  93.             base_after -= (i128)Av * (i128)prefB[L];
  94.         }
  95.         base_after -= (i128)Au * (i128)prefB[R];
  96.  
  97.         ll sumA_segment = 0;
  98.         if(R-1 >= k+1){
  99.             sumA_segment = prefA[R-1] - prefA[k];
  100.             if(k == L-1){
  101.                 sumA_segment -= Av;
  102.             }
  103.         } else {
  104.             sumA_segment = 0;
  105.         }
  106.         base_after += (i128)Bu * (i128)sumA_segment;
  107.  
  108.         ans += base_after;
  109.  
  110.         print_i128(ans);
  111.     }
  112.  
  113.     return 0;
  114. }
  115.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rD3o3X
language:
C++14 (clang 8.0)
created:
7 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!