Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.03 KB | None | 0 0
  1. /// In the Name of God
  2.  
  3. #include <bits/stdc++.h>
  4. #define pb push_back
  5. #define F first
  6. #define S second
  7. #define sq(x) (x) * (x)
  8. #define ins insert
  9. #define M_P make_pair
  10. #define sz size
  11. #define all(x) x.begin(),x.end()
  12. #define Speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  13. #define er erase
  14.  
  15. using namespace std;
  16.  
  17. typedef long long ll;
  18. typedef long double ld;
  19. typedef pair < int, int > pii;
  20. typedef pair < ll, ll > pll;
  21. typedef pair < ll, int > pli;
  22. typedef pair < int , ll > pil;
  23. typedef pair < string, string > pss;
  24. typedef pair < char, int > pci;
  25. typedef pair < char, ll > pcl;
  26. typedef pair < string, int > psi;
  27. typedef pair < string, ll > psl;
  28. typedef pair < double, double > pdd;
  29.  
  30. const int N = 222222, mod = 1e9 + 7;
  31. const ll INF = 2e18;
  32.  
  33. ll n, a[N], t[N * 4], m, z[N * 4];
  34. inline void push (ll v, ll l, ll r) {
  35. if (z[v]) {
  36. if (l != r) {
  37. t[v + v] += z[v];
  38. t[v + v + 1] += z[v];
  39. z[v + v] += z[v];
  40. z[v + v + 1] += z[v];
  41. }
  42. z[v] = 0;
  43. }
  44. }
  45. inline void build (ll v, ll l, ll r) {
  46. if (l == r) {
  47. t[v] = a[l];
  48. return;
  49. }
  50. ll md = l + ((r - l) >> 1);
  51. build (v + v, l, md);
  52. build (v + v + 1, md + 1, r);
  53. t[v] = min (t[v + v + 1], t[v + v]);
  54. }
  55. inline void updLR (ll v, ll l, ll r, ll left, ll right, ll val) {
  56. push (v, l, r);
  57. if (left > r || right < l) {
  58. return;
  59. }
  60. if (left <= l && right >= r) {
  61. t[v] += val;
  62. z[v] += val;
  63. push(v, l, r);
  64. return;
  65. }
  66. push(v, l, r);
  67. ll md = l + ((r - l) >> 1);
  68. updLR(v + v, l, md, left, right, val);
  69. updLR(v + v + 1, md + 1, r, left, right, val);
  70. t[v] = min (t[v + v], t[v + v + 1]);
  71. }
  72. inline ll get (ll v, ll l, ll r, ll left, ll right) {
  73. push(v, l, r);
  74. if (left > r || right < l) {
  75. return INF;
  76. }
  77. if (left <= l && right >= r) {
  78. push(v, l, r);
  79. return t[v];
  80. }
  81. push(v, l, r);
  82. ll md = l + ((r - l) >> 1);
  83. return min (get(v + v, l, md, left, right), get(v + v + 1, md + 1, r, left, right));
  84. }
  85. int main() {
  86. freopen ("in.txt", "r", stdin);
  87. freopen ("out.txt", "w", stdout);
  88. Speed;
  89. cin >> n;
  90. for (ll i = 1; i <= n; ++i) {
  91. cin >> a[i];
  92. }
  93. build (1, 1, n);
  94. cin >> m;
  95. while (m--) {
  96. ll x, val = 1e7, l = 1, r = 1;
  97. string s;
  98. getline (cin, s);
  99. cerr << s << "\n";
  100. ++l;
  101. ++r;
  102. if (val == 1e7) {
  103. if (l == r) {
  104. cout << a[l] << "\n";
  105. continue;
  106. }
  107. if (l < r) {
  108. cout << get (1, 1, n, l, r) << "\n";
  109. continue;
  110. }
  111. cout << min (get (1, 1, n, l, n), get(1, 1, n, 1, r)) << "\n";
  112. continue;
  113. }
  114. if (l <= r) {
  115. updLR(1, 1, n, l, r, val);
  116. continue;
  117. }
  118. updLR(1, 1, n, l, n, val);
  119. updLR(1, 1, n, 1, r, val);
  120. }
  121. return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement