fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include<algorithm>
  4. #include<string>
  5. #include<math.h>
  6. using namespace std;
  7.  
  8. const int MAX = 100000;
  9. const int MAX2 = 18;
  10.  
  11. int lookup[MAX2][MAX];
  12. int arr[MAX];
  13.  
  14. int loga[MAX];
  15.  
  16.  
  17.  
  18. int query(int L, int R)
  19. {
  20. 	int j = loga[R - L + 1];
  21. 	return min(lookup[j][L], lookup[j][R - (1 << j) + 1]);
  22. }
  23.  
  24.  
  25.  
  26. int main()
  27. {
  28. 	//freopen("sparse.in", "r", stdin);
  29. 	//freopen("sparse.out", "w", stdout);
  30. 	int n, m, a1; scanf("%d%d%d", &n, &m, &a1);
  31. 	arr[0] = a1;
  32. 	for (int i = 1; i < n; ++i)
  33. 	{
  34. 		int q = (arr[i - 1] * 23 + 21563) % (16714589);
  35. 		arr[i] = q;
  36. 	}
  37.  
  38. 	loga[0] = -1;
  39. 	for (int i = 1; i < MAX; ++i)
  40. 	{
  41. 		loga[i] = loga[i - 1];
  42. 		while ((1 << (loga[i] + 1)) <= i) loga[i]++;
  43. 	}
  44. 	int q = (int)(log2(n)) + 2;
  45.  
  46.  
  47.  
  48.  
  49.  
  50. 	//!
  51. 	for (int i = 0; i < n; ++i) lookup[0][i] = arr[i];
  52. 	for (int i = 1; i < MAX2; ++i)
  53. 		for (int j = 0; j + (1 << i) <= n; ++j)
  54. 			lookup[i][j] = min(lookup[i - 1][j], lookup[i - 1][j + (1 << (i - 1))]);
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62. 	int u1, v1; scanf("%d%d", &u1, &v1);
  63. 	int answer = query(min(u1 - 1, v1 - 1), max(u1 - 1, v1 - 1));
  64. 	for (int i = 2; i <= m; ++i)
  65. 	{
  66.  
  67. 		int u = (17 * u1 + 751 + answer + 2 * (i - 1)) % n + 1;
  68. 		int v = (13 * v1 + 593 + answer + 5 * (i - 1)) % n + 1;
  69.  
  70. 		int l = u - 1; int r = v - 1;
  71. 		if (l > r) swap(l, r);
  72.  
  73. 		int newans = query(l, r);
  74. 		u1 = u;
  75. 		v1 = v;
  76. 		answer = newans;
  77. 	}
  78. 	printf("%d %d %d", u1, v1, answer);
  79. }
Success #stdin #stdout 0s 11288KB
comments (?)
stdin 
10 8 12345
3 9
stdout 
5 3 1565158
https://ideone.com/RxiqxW
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!