fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long M = 1000000007;
  5. map <long long, bool> have;
  6. vector <long long> goRight, goLeft;
  7.  
  8. long long countLeq(vector <long long> &array, long long x)
  9. {
  10. 	long long L = -1, R = array.size(), M;
  11. 	while(R - L > 1)
  12. 	{
  13. 		M = (L + R) / 2;
  14. 		if(array[M] <= x)
  15. 			L = M;
  16. 		else
  17. 			R = M;
  18. 	}
  19. 	return L + 1;
  20. }
  21.  
  22. long long query(long long rank, long long delta)
  23. {
  24. 	long long L = -1000000000, R = 2000000000, M;
  25. 	while(R-L > 1)
  26. 	{
  27. 		M = (L + R) / 2;
  28. 		if(countLeq(goRight, M - delta) + countLeq(goLeft, M + delta) < rank + 1)
  29. 			L = M;
  30. 		else
  31. 			R = M;
  32. 	}
  33. 	return abs(R);
  34. }
  35.  
  36. int indexToRank[1000001];
  37.  
  38. class FindingKids
  39. {
  40. 	public:	long long getSum(int n, int q, int A, int B, int C)
  41. 	{
  42. 		vector <long long> pos;
  43. 		for(int i = 0; i < n; i++)
  44. 		{
  45. 			A = ((long long)A * B + C) % M;
  46. 			long long p = A % (M - n + i + 1);
  47. 			if(have.count(p))
  48. 				p = M - n + i;
  49. 			have[p] = true;
  50. 			pos.push_back(p * 1000000LL + i);
  51. 			if(p % 2 == 0)
  52. 				goRight.push_back(p);
  53. 			else
  54. 				goLeft.push_back(p);
  55. 		}
  56. 		sort(pos.begin(), pos.end());
  57. 		for(int i = 0; i < n; i++)
  58. 			indexToRank[pos[i] % 1000000] = i;
  59.  
  60. 		sort(goLeft.begin(), goLeft.end());
  61. 		sort(goRight.begin(), goRight.end());
  62. 		long long ans = 0;
  63. 		for(int i = 0; i < q; i++)
  64. 		{
  65. 			A = ((long long)A * B + C) % M;
  66. 			long long query_kid = A % n;
  67. 			A = ((long long)A * B + C) % M;
  68. 			long long query_time = A;
  69. 			ans += query(indexToRank[query_kid], query_time);
  70. 		}
  71. 		return ans;
  72. 	}
  73. };
  74.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/iXDHbE
language:
C++14 (gcc 8.3)
created:
8 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!