fork download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. using namespace std;
  21. typedef long long lld;
  22. const int MAXN = 1e5 + 10;
  23. const lld MOD = 1e9 + 7;
  24. const lld INF = 1e15;
  25.  
  26. struct P{
  27. 	lld x, y;
  28. 	P(lld _x = 0, lld _y = 0) : x(_x), y(_y) {}
  29. 	bool operator < (const P& rhs) const
  30. 	{
  31. 		if(x != rhs.x) return x < rhs.x;
  32. 		return y < rhs.y;
  33. 	}
  34. };
  35.  
  36. P p[MAXN];
  37. vector<P> np;
  38.  
  39. bool ok(lld k, int M)
  40. {
  41. 	int s = 1;
  42. 	int q = 0;
  43. 	int j = 0;
  44. 	for(int i = 0; i < np.size(); ++i){
  45. 		if(i < q) continue;
  46. 		j = i;
  47. 		while(j + 1 < np.size() && np[i].y <= np[j + 1].y + k){
  48. 			++j;
  49. 		}
  50. 		if(j + 1 == np.size()) break;
  51. 		for(q = j; q < np.size(); ++q){
  52. 			if(np[q].x > np[j].x + k) break;
  53. 		}
  54.  
  55. 		if(q == np.size()) break;
  56. 		++s;
  57. 	}
  58. 	return s <= M;
  59. }
  60.  
  61. class TheEmpireStrikesBack {
  62. public:
  63. 	int find(int AX, int BX, int CX, int AY, int BY, int CY, int N, int M) {
  64. 		p[0].x = AX;
  65. 		p[0].y = AY;
  66. 		for(int i = 1; i < N; ++i){
  67. 			p[i].x = ((1LL * p[i - 1].x * BX) + CX) % MOD;
  68. 			p[i].y = ((1LL * p[i - 1].y * BY) + CY) % MOD;
  69. 		}
  70. 		sort(p, p + N);
  71.  
  72. 		for(int i = 0; i < N; ++i){
  73. 			while(!np.empty() && np.back().x <= p[i].x && np.back().y <= p[i].y){
  74. 				np.pop_back();
  75. 			}
  76. 			np.push_back(p[i]);
  77. 		}
  78.  
  79. 		lld l = 0;
  80. 		lld r = INF;
  81. 		while(l < r){
  82. 			lld mid = (l + r) >> 1;
  83. 			if(ok(mid, M)){
  84. 				r = mid;	
  85. 			}else{
  86. 				l = mid + 1;
  87. 			}
  88. 		}
  89. 		return l;
  90. 	}
  91. };
  92.  
  93.  
  94. <%:testing-code%>
  95. //Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:94:1: error: expected unqualified-id before '<%' token
 <%:testing-code%>
 ^
stdout
copy 
Standard output is empty
https://ideone.com/LNXnwt
SRM 678 Div1 500
language:
C++14 (gcc 8.3)
created:
9 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!