Advertisement
bibaboba12345

Untitled

Jan 8th, 2023
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.91 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <string>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <deque>
  11. #include <set>
  12. #include <map>
  13. #include <climits>
  14. #include <cstdlib>
  15. #include<time.h>
  16. #include<iomanip>
  17. using namespace std;
  18. const int N = 2e5 + 7;
  19. long long a[N], s[N],i,n,q,mx,summ,l,cnt,vic,add;
  20. struct query {
  21. int num;
  22. long long mx,sum, cnt;
  23. };
  24. bool comp1(query a, query b) {
  25. if (a.mx == b.mx) {
  26. return a.num < b.num;
  27. }
  28. return a.mx < b.mx;
  29. }
  30. bool comp2(query a, query b) {
  31. return a.num < b.num;
  32. }
  33. query Q[N];
  34. void solve() {
  35. mx = Q[0].mx;
  36. l = 0;
  37. summ = 0;
  38. cnt = 0;
  39. for (i = 0; i < n-1; i++) {
  40. add = (a[i + 1] - 1 - summ) / a[i];
  41. cnt += add;
  42. summ += add * a[i];
  43. if (summ == mx) {
  44. //cout << summ << " " << cnt << "\n";
  45. Q[l].sum = summ;
  46. Q[l].cnt = cnt;
  47. l++;
  48. mx = Q[l].mx;
  49. i--;
  50. if (l == q) {
  51. return;
  52. }
  53. }
  54. if (summ > mx) {
  55. if ((summ - mx) % a[i] == 0) {
  56. vic = (summ - mx) / a[i];
  57. }
  58. else {
  59. vic = (summ - mx) / a[i] + 1;
  60. }
  61. Q[l].sum = summ - vic * a[i];
  62. Q[l].cnt = cnt - vic;
  63. l++;
  64. mx = Q[l].mx;
  65. i--;
  66. if (l == q) {
  67. return;
  68. }
  69. }
  70. }
  71. while(l < q){
  72. if (summ < mx) {
  73. vic = (mx - summ) / a[n - 1];
  74. Q[l].cnt = cnt + vic;
  75. Q[l].sum = summ + vic * a[n - 1];
  76. l++;
  77. mx = Q[l].mx;
  78. }
  79. else {
  80. Q[l].cnt = cnt;
  81. Q[l].sum = summ;
  82. l++;
  83. mx = Q[l].mx;
  84. }
  85. }
  86.  
  87. }
  88.  
  89. int main() {
  90. std::ios::sync_with_stdio(false);
  91. cin.tie(0);
  92. cout.tie(0);
  93. cin >> n;
  94. for (i = 0; i < n; i++) {
  95. cin >> a[i];
  96. }
  97. cin >> q;
  98. for (int I = 0; I < q; I++) {
  99. cin >> Q[I].mx;
  100. Q[I].num = I;
  101. }
  102. sort(Q, Q + q,comp1);
  103. solve();
  104. sort(Q, Q + q, comp2);
  105. for (i = 0; i < q; i++) {
  106. cout << Q[i].sum << " " << Q[i].cnt << "\n";
  107. }
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement