Guest User

Untitled

a guest
Nov 20th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define mp make_pair
  5. #define fs first
  6. #define sc second
  7. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  8.  
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12.  
  13. const int t_sz = 270000;
  14. const int K = 360;
  15. const int maxn = 128100;
  16. ll sum_x[maxn];
  17. int a[maxn];
  18. int b[maxn];
  19. int A[maxn];
  20. int B[maxn];
  21. map<int, int> ma, mb;
  22. vector<pair<pair<int, int>, int> > q[maxn / K + 10];
  23. ll sum[t_sz];
  24. int cnt[t_sz];
  25. int ans[100100];
  26.  
  27. bool cmp(const pair<pair<int, int>, int> &a,
  28. const pair<pair<int, int>, int> &b) {
  29. return a.fs.sc < b.fs.sc;
  30. }
  31.  
  32. void upd(int v, int l, int r, int i, int val, int Al) {
  33. if (l == r - 1) {
  34. cnt[v] += val;
  35. sum[v] += Al * val;
  36. return;
  37. }
  38. int m = (l + r) / 2;
  39. if (i < m) {
  40. upd(v * 2, l, m, i, val, Al);
  41. } else {
  42. upd(v * 2 + 1, m, r, i, val, Al);
  43. }
  44. sum[v] = sum[v * 2] + sum[v * 2 + 1];
  45. cnt[v] = cnt[v * 2] + cnt[v * 2 + 1];
  46. }
  47.  
  48. int get_sum(int v, int l, int r, int k) {
  49. if (l == r - 1) {
  50. int cur = min(cnt[v], k);
  51. return cur * (sum[v] / cnt[v]);
  52. }
  53. int m = (l + r) / 2;
  54. if (k == cnt[2 * v + 1]) {
  55. return sum[2 * v + 1];
  56. } else if (k < cnt[2 * v + 1]) {
  57. return get_sum(2 * v + 1, m, r, k);
  58. } else {
  59. return sum[2 * v + 1] + get_sum(2 * v, l, m, k - cnt[2 * v + 1]);
  60. }
  61. }
  62.  
  63. int main() {
  64. int n;
  65. cin >> n;
  66. forn (i, n) {
  67. cin >> a[i];
  68. }
  69. forn (i, n) {
  70. cin >> b[i];
  71. }
  72. forn (i, n) {
  73. int x = min(a[i], b[i]);
  74. a[i] -= x;
  75. b[i] -= x;
  76. sum_x[i + 1] = sum_x[i] + x;
  77. }
  78. forn (i, n) {
  79. A[i] = a[i];
  80. }
  81. sort(A, A + n);
  82. forn (i, n) {
  83. ma[A[i]] = i;
  84. }
  85. forn (i, n) {
  86. B[i] = b[i];
  87. }
  88. sort(B, B + n);
  89. forn (i, n) {
  90. mb[B[i]] = i;
  91. }
  92. forn (i, n) {
  93. a[i] = ma[a[i]];
  94. b[i] = mb[b[i]];
  95. }
  96. int m;
  97. cin >> m;
  98. forn (i, m) {
  99. int l, r;
  100. cin >> l >> r;
  101. --l;
  102. ans[i] += (sum_x[r] - sum_x[l]) * 2;
  103. q[l / K].pb(mp(mp(l, r), i));
  104. }
  105. forn (i, maxn / K + 1) {
  106. sort(q[i].begin(), q[i].end(), cmp);
  107. }
  108. forn (i, maxn / K + 1) {
  109. forn (j, t_sz) {
  110. cnt[j] = sum[j] = 0;
  111. }
  112. int l = K * i, r = l;
  113. forn (j, q[i].size()) {
  114. int nl = q[i][j].fs.fs, nr = q[i][j].fs.sc;
  115. while (l < nl) {
  116. upd(1, 0, n, a[l], -1, A[a[l]]);
  117. ++l;
  118. }
  119. while (l > nl) {
  120. --l;
  121. upd(1, 0, n, a[l], 1, A[a[l]]);
  122. }
  123. while (r < nr) {
  124. upd(1, 0, n, a[r], 1, A[a[r]]);
  125. ++r;
  126. }
  127. while (r > nr) {
  128. --r;
  129. upd(1, 0, n, a[r], -1, A[a[r]]);
  130. }
  131. ans[q[i][j].sc] += get_sum(1, 0, n, 2 * (r - l) / 3);
  132. ans[q[i][j].sc] += get_sum(1, 0, n, (r - l) / 3);
  133. }
  134. }
  135. forn (i, maxn / K + 1) {
  136. forn (j, t_sz) {
  137. cnt[j] = sum[j] = 0;
  138. }
  139. int l = K * i, r = l;
  140. forn (j, q[i].size()) {
  141. int nl = q[i][j].fs.fs, nr = q[i][j].fs.sc;
  142. while (l < nl) {
  143. upd(1, 0, n, b[l], -1, B[b[l]]);
  144. ++l;
  145. }
  146. while (l > nl) {
  147. --l;
  148. upd(1, 0, n, b[l], 1, B[b[l]]);
  149. }
  150. while (r < nr) {
  151. upd(1, 0, n, b[r], 1, B[b[r]]);
  152. ++r;
  153. }
  154. while (r > nr) {
  155. --r;
  156. upd(1, 0, n, b[r], -1, B[b[r]]);
  157. }
  158. ans[q[i][j].sc] += get_sum(1, 0, n, 2 * (r - l) / 3);
  159. ans[q[i][j].sc] += get_sum(1, 0, n, (r - l) / 3);
  160. }
  161. }
  162. forn (i, m) {
  163. cout << (ans[i] / 2);
  164. if (ans[i] % 2) {
  165. cout << ".5";
  166. }
  167. cout << endl;
  168. }
  169. }
Add Comment
Please, Sign In to add comment