fork(2) download 
  1. #include <iostream>
  2. #include <utility>
  3. #include <algorithm>
  4. #define SIZE 100000
  5. using namespace std;
  6.  
  7. void build(pair<int, int>* tree, int pos, int l, int r)
  8. {
  9. 	if (l == r)
  10. 	{
  11. 		tree[pos].first = (l % 12345) * (l % 12345) % 12345 + ((l % 23456) * (l % 23456) % 23456) * (l % 23456) % 23456;
  12. 		tree[pos].second = tree[pos].first;
  13. 	}
  14. 	else
  15. 	{
  16. 		int m = (l + r) / 2;
  17. 		build(tree, pos * 2, l, m);
  18. 		build(tree, pos * 2 + 1, m + 1, r);
  19. 		tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
  20. 	}
  21. }
  22.  
  23. pair<int, int> get(pair<int, int>* tree, int pos, int l, int r, int ql, int qr)
  24. {
  25. 	if (l == ql && r == qr)
  26. 		return tree[pos];
  27. 	else
  28. 	{
  29. 		int m = (l + r) / 2;
  30. 		if (qr <= m)
  31. 			return get(tree, pos * 2, l, m, ql, qr);
  32. 		else if (ql >= m + 1)
  33. 			return get(tree, pos * 2 + 1, m + 1, r, ql, qr);
  34. 		else
  35. 		{
  36. 			pair<int, int> a = get(tree, pos * 2, l, m, ql, m);
  37. 			pair<int, int> b = get(tree, pos * 2 + 1, m + 1, r, m + 1, qr);
  38. 			return make_pair(max(a.first, b.first), min(a.second, b.second));
  39. 		}
  40. 	}
  41. }
  42.  
  43. void modify(pair<int, int>* tree, int pos, int l, int r, int npos, int nv)
  44. {
  45. 	if (l == r)
  46. 	{
  47. 		tree[pos].first = nv;
  48. 		tree[pos].second = nv;
  49. 	}
  50. 	else
  51. 	{
  52. 		int m = (l + r) / 2;
  53. 		if (npos <= m)
  54. 			modify(tree, pos * 2, l, m, npos, nv);
  55. 		else
  56. 			modify(tree, pos * 2 + 1, m + 1, r, npos, nv);
  57. 		tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
  58. 	}
  59. }
  60.  
  61. int main() 
  62. {
  63. 	ios::sync_with_stdio(false);
  64. 	pair<int, int> tree[SIZE * 4];
  65. 	build(tree, 1, 1, SIZE);
  66. 	int n, x, y;
  67. 	cin >> n;
  68. 	for (int i = 0; i < n; i++)
  69. 	{
  70. 		cin >> x >> y;
  71. 		if (x > 0)
  72. 		{
  73. 			pair<int, int> query = get(tree, 1, 1, SIZE, x, y);
  74. 			cout << query.first - query.second << endl;
  75. 		}
  76. 		else
  77. 			modify(tree, 1, 1, SIZE, -x, y);
  78. 	}
  79. 	return 0;
  80. }
Success #stdin #stdout 0.01s 6460KB
comments (?)
stdin 
13
1 17
-5 -400
-3 500
3 5
1 17
-2 345
2 345
2 3
2 5
-1 -100000
-2 100000
1 2
1 100000
stdout 
5200
900
5602
35813
155
900
200000
200000
https://ideone.com/sI589p
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!