fork download
copy 
  1. #include <bits/stdc++.h>
  2. namespace ada {
  3. class Xoroshiro128 {
  4.  public:
  5.   using result_type = uint32_t;
  6.   static constexpr result_type(min)() { return 0; }
  7.   static constexpr result_type(max)() { return UINT32_MAX; }
  8.   static inline result_type rotl(const result_type x, int k) {
  9.     return (x << k) | (x >> (32 - k));
  10.   }
  11.   Xoroshiro128() : Xoroshiro128(1, 2, 3, 4) {}
  12.   Xoroshiro128(result_type a, result_type b, result_type c, result_type d)
  13.       : s{a, b, c, d} {}
  14.   result_type operator()() {
  15.     const result_type result = rotl(s[0] + s[3], 7) + s[0];
  16.     const result_type t = s[1] << 9;
  17.     s[2] ^= s[0];
  18.     s[3] ^= s[1];
  19.     s[1] ^= s[2];
  20.     s[0] ^= s[3];
  21.     s[2] ^= t;
  22.     s[3] = rotl(s[3], 11);
  23.     return result;
  24.   }
  25.  
  26.  private:
  27.   std::array<result_type, 4> s;
  28. };
  29.  
  30. namespace {
  31. 	int c_lead, c_team;
  32. 	Xoroshiro128 rng;
  33. 	}  // namespace
  34.  
  35. 	int Init() {
  36. 	  int n;
  37. 	  uint32_t s1, s2, s3, s4;
  38. 	  std::cin >> n >> c_lead >> c_team >> s1 >> s2 >> s3 >> s4;
  39. 	  rng = Xoroshiro128(s1, s2, s3, s4);
  40. 	  return n;
  41. 	}
  42.  
  43. 	int GetLeadership() { return uint64_t(rng()) * c_lead >> 32; }
  44.  
  45. 	int GetTeamValue() {
  46. 	  int tmp = int(uint64_t(rng()) * c_team >> 32) + 1;
  47. 	  return int(c_team / sqrt(tmp));
  48. 	}
  49.  
  50. }  // namespace ada
  51. using namespace std;
  52. typedef long long ll;
  53. const ll mod = 1e9 + 7, INF = 1LL << 60;
  54. const int maxn = 2e6 + 5;
  55. int leadership[maxn], team_value[maxn];
  56. ll prefix[maxn], seg[4 * maxn], lazy[4 * maxn];
  57. inline void push(int index, int left, int right) {
  58. 	if (lazy[index]) {
  59. 		if (left != right) {
  60. 			seg[2 * index] += lazy[index];
  61. 			seg[2 * index + 1] += lazy[index];
  62. 			lazy[2 * index] += lazy[index];
  63. 			lazy[2 * index + 1] += lazy[index];
  64. 		}
  65. 		lazy[index] = 0;
  66. 	}
  67. }
  68. void update(int index, int left, int right, int lo, int hi, ll val) {
  69. 	push(index, left, right);
  70. 	if (lo <= left && right <= hi) {
  71. 		seg[index] += val;
  72. 		lazy[index] += val;
  73. 		push(index, left, right);
  74. 		return;
  75. 	}
  76. 	int mid = (left + right) / 2;
  77. 	if (hi <= mid)
  78. 		update(2 * index, left, mid, lo, hi, val);
  79. 	else if (lo > mid)
  80. 		update(2 * index + 1, mid + 1, right, lo, hi, val);
  81. 	else {
  82. 		update(2 * index, left, mid, lo, hi, val);
  83. 		update(2 * index + 1, mid + 1, right, lo, hi, val);
  84. 	}
  85. 	seg[index] = max(seg[2 * index], seg[2 * index + 1]);
  86. }
  87. int query(int index, int left, int right, int val) {
  88. 	push(index, left, right);
  89. 	if (left == right)
  90. 		return left;
  91. 	int mid = (left + right) / 2;
  92. 	if (seg[2 * index + 1] <= val)
  93. 		return query(2 * index, left, mid, val);
  94. 	else
  95. 		return query(2 * index + 1, mid + 1, right, val);
  96. }
  97.  
  98. int main() {
  99. 	ios::sync_with_stdio(0);
  100. 	cin.tie(0);
  101. 	int n = ada::Init();
  102. 	for (int i = n; i > 0; --i)
  103. 		leadership[i] = ada::GetLeadership();
  104. 	for (int i = n; i > 0; --i)
  105. 		team_value[i] = ada::GetTeamValue();
  106. 	prefix[0] = 1;
  107. 	update(1, 0, n, 0, 0, INF);
  108. 	for (int i = 1; i <= n; ++i) {
  109. 		int ind = query(1, 0, n, leadership[i]);
  110. 		if (ind == 0)
  111. 			prefix[i] = 2 * prefix[i - 1] % mod;
  112. 		else
  113. 			prefix[i] = (2 * prefix[i - 1] - prefix[ind - 1] + mod) % mod;
  114. 		update(1, 0, n, 0, i, team_value[i]);
  115. 	}
  116. 	cout << (prefix[n] - prefix[n - 1] + mod) % mod << '\n';
  117. 	return 0;
  118. }
Success #stdin #stdout 0s 4420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/A75S6x
language:
C++ (gcc 8.3)
created:
4 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!