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