Advertisement
Guest User

Untitled

a guest
Jan 25th, 2020
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.46 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, m, q, i, pozmax, pozmin, rezultat;
  4. long long sum[200002];
  5.  
  6. struct valori
  7. {
  8. int original, suma;
  9. }v[100001];
  10. struct pozitii
  11. {
  12. int a, b, c, d;
  13. } poz[100001];
  14.  
  15. int cautmax(int st, int dr, int x)
  16. {
  17. if (st > dr) return -1;
  18. else
  19. {
  20. int mij = (st + dr) / 2;
  21. if (x > v[dr].original) {
  22. return dr;
  23. }
  24. if (x < v[st].original) {
  25. return st - 1;
  26. }
  27. if (x < v[mij].original)
  28. return cautmax(st, mij - 1, x);
  29. else
  30. return cautmax(mij + 1, dr, x);
  31. }
  32. }
  33. int cautmin(int st, int dr, int x)
  34. {
  35. int mij = (st + dr) / 2;
  36. if (x == v[mij].original) {
  37. return x;
  38. }
  39. if (x > v[dr].original) {
  40. return dr + 1;
  41. }
  42. if (x < v[st].original) {
  43. return st;
  44. }
  45. if (x < v[mij].original)
  46. return cautmax(st, mij - 1, x);
  47. else
  48. return cautmax(mij + 1, dr, x);
  49. }
  50. void citire()
  51. {
  52. cin >> n >> m;
  53. for (i = 1; i <= n; ++i)
  54. {
  55. cin >> v[i].original;
  56. }
  57. cin >> q;
  58. for (i = 1; i <= q; i++)
  59. cin >> poz[i].a >> poz[i].b >> poz[i].c >> poz[i].d;
  60. }
  61. int main()
  62. {
  63. citire();
  64. v[1].suma = v[1].original;
  65. for (i = 2; i <= n; i++)
  66. {
  67. v[i].suma = v[i - 1].original + v[i].original;
  68. }
  69. for (i = 1; i <= q; ++i)
  70. {
  71. pozmin = cautmin(poz[i].a, poz[i].c, poz[i].b);
  72. pozmax = cautmax(pozmin, poz[i].c, poz[i].d);
  73. rezultat = v[pozmax].suma - v[pozmin - 1].suma - poz[i].b * (pozmax - pozmin + 1) + (poz[i].c - pozmax) * (poz[i].d - poz[i].b);
  74. cout << rezultat << '\n';
  75. }
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement