fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iomanip>
  6. #include <numeric>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <string>
  11.  
  12. #define hyathu main
  13. #define popcorn __builtin_popcount
  14.  
  15. using namespace std;
  16. using ll = long long;
  17. using ull = unsigned long long;
  18. using ld = long double;
  19. using pint = int*;
  20.  
  21. constexpr int mmb = 1e5 + 69;
  22. const ld pi = atan(1) * 4;
  23.  
  24. int n, m;
  25. struct Prob{
  26.     ll a, b;
  27. } p[mmb], aft[mmb];
  28.  
  29. ll ans[mmb], ab[mmb], sa[mmb];
  30.  
  31. int id[mmb], ind[mmb];
  32.  
  33. int qa[mmb], qb[mmb];
  34.  
  35. void readData(){
  36.     cin >> n >> m;
  37.     for(int i = 1; i <= n; ++i)
  38.         cin >> p[i].a;
  39.     for(int i = 1; i <= n; ++i)
  40.         cin >> p[i].b;
  41.  
  42.     iota(id + 1, id + n + 1, 1);
  43. }
  44.  
  45. void solve(){
  46.     sort(id + 1, id + n + 1, [](int x, int y){
  47.         if(p[x].b == p[y].b)
  48.             return p[x].a > p[y].a;
  49.         return p[x].b < p[y].b;
  50.     });
  51.  
  52.     for(int i = 1; i <= n; ++i){
  53.         int d = id[i];
  54.         aft[i] = p[d];
  55.         ind[d] = i;
  56.     }
  57.  
  58.     ans[0] = 0, ab[0] = 0;
  59.     for(int i = 1; i <= n; ++i){
  60.         ab[i] = ab[i - 1] + aft[i].b;
  61.         ans[i] = ans[i - 1] + ab[i] * aft[i].a;
  62.         sa[i] = sa[i - 1] + aft[i].a;
  63.     }
  64.  
  65.     int x, y;
  66.  
  67. while(m--){
  68.     cin >> x >> y;
  69. //    cout << x << " " << y << " ";
  70.     if(ind[x] < ind[y]){
  71.         cout << ans[n] << "\n";
  72.         continue;
  73.     }
  74. //    cout << "\n";
  75.  
  76.     int tmp = y;
  77.     y = ind[x], x = ind[tmp];
  78. //    cout << x << " " << y << " ";
  79.  
  80.     ll mid = ans[y] - ans[x];
  81.  
  82. //    cout << mid << " " << ab[y] << "\n";
  83.  
  84.     mid -= (sa[y] - sa[x]) * aft[x].b;
  85. //    cout << mid << "-\n";
  86.  
  87.     cout << ans[x - 1] + mid + aft[x].a * ab[y] + ans[n] - ans[y] << "\n";
  88. }
  89. }
  90.  
  91. #define filename "test"
  92.  
  93. int hyathu(){
  94.     ios_base::sync_with_stdio(false);
  95.     cin.tie(NULL);
  96.     cout.tie(NULL);
  97.  
  98.     #ifdef dangheo
  99.     freopen("test.inp", "r", stdin);
  100.     //freopen("test.out", "w", stdout);
  101.     #else
  102.     //freopen(filename".INP", "r", stdin);
  103.     //freopen(filename".OUT", "w", stdout);
  104.     #endif
  105.  
  106.     readData();
  107.     solve();
  108.  
  109.     return 0;
  110. }
  111.  
Success #stdin #stdout 0.01s 5592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2TPr6r
language:
C++ (gcc 8.3)
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!