Advertisement
Guest User

Untitled

a guest
Aug 26th, 2020
682
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. using namespace std;
  5. const int mod = 1e9 + 7;
  6.  
  7. vector<int> h, w, pref;
  8. int ans = 0;
  9.  
  10. int bpow(int a, int n) {
  11. int res = 1;
  12. while(n > 0) {
  13. if(n & 1) {
  14. res *= a;
  15. res %= mod;
  16. }
  17. a *= a;
  18. a %= mod;
  19. n /= 2;
  20. }
  21. return res;
  22. }
  23.  
  24. int C(int n, int k = 2) {
  25. int res = 1;
  26. for(int i = 1; i <= k; i++) {
  27. res = ((res * ((n - k + i) % mod)) % mod) * bpow(i, mod - 2);
  28. }
  29. return res;
  30. }
  31.  
  32.  
  33. //sub4
  34. void solvesame() {
  35. int y = h[0];
  36. int x = 0;
  37. for(auto it: w) {
  38. x = (x + it) % mod;
  39. }
  40. cout << ((C(x + 1, 2) % mod) * (C(y + 1, 2) % mod)) % mod << endl;
  41. }
  42.  
  43. //sub3
  44. void solvesub3() {
  45. int n = h.size();
  46. int x = 0;
  47. for(auto it: w) {
  48. x = (x + it) % mod;
  49. }
  50. int ans = ((C(x + 1, 2) % mod));
  51. int prev = 0;
  52. for(int i = 0; i < n; i++) {
  53. if(h[i] == 1) {
  54. ans = (ans + ((C(prev + 1, 2) % mod) * (C(3, 2) % mod)) % mod) % mod;
  55. ans = (ans - (C(prev + 1, 2) % mod) + mod) % mod;
  56. prev = 0;
  57. } else {
  58. prev += w[i];
  59. }
  60. }
  61. ans = (ans + ((C(prev + 1, 2) % mod) * (C(3, 2) % mod)) % mod) % mod;
  62. ans = (ans - (C(prev + 1, 2) % mod) + mod) % mod;
  63. cout << ans << endl;
  64. }
  65.  
  66. void solvesub5() {
  67. int n = h.size();
  68. int x = 0;
  69. for(auto it: w) {
  70. x = (x + it) % mod;
  71. }
  72. int ans = ((C(x + 1, 2) % mod) * (C(h[0] + 1, 2) % mod)) % mod;
  73. x = (x - w[0] + mod) % mod;
  74. for(int i = 1; i < n; i++) {
  75. ans = (ans + ((C(x + 1, 2) % mod) * (C(h[i] + 1, 2) % mod)) % mod) % mod;
  76. ans = (ans - ((C(x + 1, 2) % mod) * (C(h[i - 1] + 1, 2) % mod)) % mod + mod) % mod;
  77. x = (x - w[i] + mod) % mod;
  78. }
  79. cout << ans << endl;
  80. }
  81.  
  82. void solvesub2() {
  83. int mxh = *max_element(h.begin(), h.end());
  84. int ans = 0;
  85. int n = h.size();
  86.  
  87. for(int hi = 1; hi <= mxh; hi++) {
  88. int prev = 0;
  89. for(int i = 0; i < n; i++) {
  90. if(h[i] >= hi) {
  91. prev = (prev + w[i]) % mod;
  92. } else {
  93. ans = (ans + ((C(prev + 1, 2) % mod) * (C(hi + 1, 2) % mod)) % mod) % mod;
  94. ans = (ans - ((C(prev + 1, 2) % mod) * (C(hi, 2) % mod)) % mod + mod) % mod;
  95. prev = 0;
  96. }
  97. }
  98. ans = (ans + ((C(prev + 1, 2) % mod) * (C(hi + 1, 2) % mod)) % mod) % mod;
  99. ans = (ans - ((C(prev + 1, 2) % mod) * (C(hi, 2) % mod)) % mod + mod) % mod;
  100. }
  101. cout << ans << endl;
  102. }
  103.  
  104. void solvesub6() {
  105. int ans = 0;
  106. int n = h.size();
  107. vector<int> his = h;
  108. sort(his.begin(), his.end());
  109. for(int hi = 0; hi < n; hi++) {
  110. int prev = 0;
  111. for(int i = 0; i < n; i++) {
  112. if(h[i] >= his[hi]) {
  113. prev = (prev + w[i]) % mod;
  114. } else {
  115. ans = (ans + ((C(prev + 1, 2) % mod) * (C(his[hi] + 1, 2) % mod)) % mod) % mod;
  116. if(hi > 0) ans = (ans - ((C(prev + 1, 2) % mod) * (C(his[hi - 1] + 1, 2) % mod)) % mod + mod) % mod;
  117. prev = 0;
  118. }
  119. }
  120. ans = (ans + ((C(prev + 1, 2) % mod) * (C(his[hi] + 1, 2) % mod)) % mod) % mod;
  121. if(hi > 0) ans = (ans - ((C(prev + 1, 2) % mod) * (C(his[hi - 1] + 1, 2) % mod)) % mod + mod) % mod;
  122. }
  123. cout << ans << endl;
  124. }
  125. main() {
  126. boost;
  127. int n;
  128. cin >> n;
  129. h.resize(n), w.resize(n), pref.resize(n + 1);
  130. for(int i = 0; i < n; i++) {
  131. cin >> h[i];
  132. }
  133. for(int i = 0; i < n; i++) {
  134. cin >> w[i];
  135. pref[i + 1] = pref[i] + w[i];
  136. }
  137.  
  138. //subtasks
  139. bool sub4 = 1;
  140. bool sub3 = (h[0] <= 2);
  141. bool sub5 = 1;
  142. bool sub2 = (n <= 50 && h[0] <= 50);
  143. bool sub6 = (n <= 1000);
  144. //end subtasks
  145.  
  146. //check subtask
  147. for(int i = 1; i < n; i++) {
  148. sub4 &= (h[i] == h[i - 1]);
  149. sub3 &= (h[i] <= 2);
  150. sub5 &= (h[i - 1] <= h[i]);
  151. sub2 &= (h[i] <= 50);
  152. }
  153.  
  154. if(sub2) {
  155. solvesub2();
  156. return 0;
  157. }
  158. if(sub3) {
  159. solvesub3();
  160. return 0;
  161. }
  162. if(sub4) {
  163. solvesame();
  164. return 0;
  165. }
  166. if(sub5) {
  167. solvesub5();
  168. return 0;
  169. }
  170. if(sub6) {
  171. solvesub6();
  172. return 0;
  173. }
  174. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement