fork download
copy 
  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[MAX][MAX2];
  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[L][j], lookup[R - (1 << j) + 1][j]);
  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. 	//!
  52. 	for (int i = 0; i < n; i++) lookup[i][0] = arr[i];
  53. 	for (int j = 1; j < MAX2; j++)
  54. 		for (int i = 0; i + (1 << j)  <= n; i++)
  55. 				lookup[i][j] = min(lookup[i][j - 1], lookup[i + (1 << (j - 1))][j - 1]);
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65. 	int u1, v1; scanf("%d%d", &u1, &v1);
  66. 	int answer = query(min(u1 - 1, v1 - 1), max(u1 - 1, v1 - 1));
  67. 	for (int i = 2; i <= m; ++i)
  68. 	{
  69.  
  70. 		int u = (17 * u1 + 751 + answer + 2 * (i - 1)) % n + 1;
  71. 		int v = (13 * v1 + 593 + answer + 5 * (i - 1)) % n + 1;
  72.  
  73. 		int l = u - 1; int r = v - 1;
  74. 		if (l > r) swap(l, r);
  75.  
  76. 		int newans = query(l, r);
  77. 		u1 = u;
  78. 		v1 = v;
  79. 		answer = newans;
  80. 	}
  81. 	printf("%d %d %d", u1, v1, answer);
  82. }
Success #stdin #stdout 0s 11288KB
comments (?)
stdin
copy 
10 8 12345
3 9
stdout
copy 
5 3 1565158
https://ideone.com/4L1YCL
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!