fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define endl "\n"
  5.  
  6. auto random_address = []
  7. { char *p = new char; delete p; return uint64_t(p); };
  8. const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1);
  9. std::mt19937 rnd(SEED);
  10. #define rng(l, r) uniform_int_distribution<int64_t>(l, r)(rnd)
  11. /*
  12. Large Primes for hash
  13. 1000000007
  14. 10000000019
  15. 100000000003
  16. 1000000000039
  17. 10000000000037
  18. 100000000000031
  19. 1000000000000037
  20. 10000000000000061
  21. 2305843009213693951 = (1LL << 61) - 1
  22. */
  23. constexpr ll mod = 10000000019; // Large prime,
  24. // Takes more time, choose a smaller prime and omit mult64() for faster code but higher probability of collision
  25. // constexpr ll mod = 1e9 + 7; // Is usually sufficient for most of the hashing problems
  26.  
  27. inline ll mult64(const ll &a, const ll &b)
  28. {
  29. 	return __int128_t(a) * b % mod;
  30. }
  31. ll modPow(ll N, ll power, ll mod)
  32. {
  33. 	ll res{1};
  34. 	while (power)
  35. 	{
  36. 		if (power & 1)
  37. 			res = mult64(res, N);
  38. 		N = mult64(N, N);
  39. 		power >>= 1;
  40. 	}
  41. 	return res;
  42. }
  43. ll b1 = rng(100, 100000), b2 = rng(1000, 100000);
  44. ll b1I = modPow(b1, mod - 2, mod), b2I = modPow(b2, mod - 2, mod);
  45. vector<ll> Pb1, Pb2, sumB1, sumB2;
  46. void pre(ll maxSize)
  47. {
  48. 	Pb1 = Pb2 = sumB1 = sumB2 = vector<ll>(maxSize + 1, 1);
  49. 	for (int i = 1; i <= maxSize; i++)
  50. 	{
  51. 		Pb1[i] = mult64(Pb1[i - 1], b1);
  52. 		Pb2[i] = mult64(Pb2[i - 1], b2);
  53. 		sumB1[i] = ((sumB1[i - 1] + Pb1[i]) % mod);
  54. 		sumB2[i] = ((sumB2[i - 1] + Pb2[i]) % mod);
  55. 	}
  56. }
  57. class Hash
  58. {
  59. 	using pll = pair<ll, ll>;
  60. 	ll plus(const ll &x, const ll &y)
  61. 	{
  62. 		return ((__int128_t(x) + y + mod) % mod);
  63. 	}
  64.  
  65. public:
  66. 	pll code{};
  67. 	int size{};
  68. 	explicit Hash(pair<ll, ll> x = {}, ll sz = {}) : code(std::move(x)), size(sz) {}
  69.  
  70. 	Hash(const ll &x) : code({x % mod, x % mod}), size(1) {}
  71.  
  72. 	Hash(const string &x) : code(), size(0)
  73. 	{
  74. 		for (const char &c : x)
  75. 			*this = *(this) + c;
  76. 	}
  77.  
  78. 	void pop_front(int x)
  79. 	{
  80. 		code.first = (code.first - mult64(Pb1[--size], x) + mod) % mod;
  81. 		code.second = (code.second - mult64(Pb2[size], x) + mod) % mod;
  82. 	}
  83.  
  84. 	void pop_back(int x)
  85. 	{
  86. 		code.first = mult64((code.first - x + mod), b1I);
  87. 		code.second = mult64((code.second - x + mod), b2I);
  88. 		size--;
  89. 	}
  90. 	void clear()
  91. 	{
  92. 		code = {}, size = 0;
  93. 	}
  94. 	Hash operator+(const Hash &o)
  95. 	{
  96. 		Hash ans;
  97. 		ans.code = {plus(mult64(code.first, Pb1[o.size]), o.code.first),
  98. 					plus(mult64(code.second, Pb2[o.size]), o.code.second)};
  99. 		ans.size = size + o.size;
  100. 		return ans;
  101. 	}
  102. 	friend Hash operator+(const Hash &f, const Hash &o)
  103. 	{
  104. 		return Hash({((mult64(f.code.first, Pb1[o.size]) + o.code.first) % mod),
  105. 					 ((mult64(f.code.second, Pb2[o.size]) + o.code.second) % mod)},
  106. 					f.size + o.size);
  107. 	}
  108. 	bool operator<(const Hash &o) const
  109. 	{
  110. 		if (code == o.code)
  111. 			return size < o.size;
  112. 		return code < o.code;
  113. 	}
  114. 	bool operator>(const Hash &o) const
  115. 	{
  116. 		if (code == o.code)
  117. 			return size > o.size;
  118. 		return code > o.code;
  119. 	}
  120. 	bool operator>=(const Hash &o) const
  121. 	{
  122. 		if (code == o.code)
  123. 			return (size >= o.size);
  124. 		return code > o.code;
  125. 	}
  126. 	bool operator==(const Hash &o) const
  127. 	{
  128. 		return size == o.size && code == o.code;
  129. 	}
  130. 	bool operator!=(const Hash &o) const
  131. 	{
  132. 		return size != o.size || code != o.code;
  133. 	}
  134. };
  135.  
  136. // Rabin-Karp Algorithm
  137. struct HashRange
  138. {
  139. 	vector<Hash> p, s;
  140. 	HashRange(const string &t) : p(t.size()), s(t.size())
  141. 	{
  142. 		if (t.empty())
  143. 			return;
  144. 		p.front() = t.front();
  145. 		for (int i = 1; i < t.size(); i++)
  146. 			p[i] = p[i - 1] + t[i];
  147. 		s.back() = t.back();
  148. 		for (int i = int(t.size()) - 2; i >= 0; i--)
  149. 			s[i] = s[i + 1] + t[i];
  150. 	}
  151. 	Hash get(int l, int r) const // 0-based indices
  152. 	{
  153. 		if (l > r)
  154. 			return Hash();
  155. 		if (!l)
  156. 			return p[r];
  157. 		return Hash({(p[r].code.first - mult64(p[l - 1].code.first, Pb1[r - l + 1]) + mod) % mod,
  158. 					 (p[r].code.second - mult64(p[l - 1].code.second, Pb2[r - l + 1]) + mod) % mod},
  159. 					r - l + 1);
  160. 	}
  161. 	Hash inv(int l, int r) const // 0-based indices
  162. 	{
  163. 		if (l > r)
  164. 			return Hash();
  165. 		if (r + 1 == s.size())
  166. 			return s[l];
  167. 		return Hash({(s[l].code.first - mult64(s[r + 1].code.first, Pb1[r - l + 1]) + mod) % mod,
  168. 					 (s[l].code.second - mult64(s[r + 1].code.second, Pb2[r - l + 1]) + mod) % mod},
  169. 					r - l + 1);
  170. 	}
  171. };
  172. /////////////////////////////////////////////
  173.  
  174. namespace SuffixArray
  175. {
  176. 	const int maxN = (1000001);
  177. 	string S;
  178. 	int N, gap;
  179. 	int SA[maxN], pos[maxN], tmp[maxN], lcp[maxN];
  180.  
  181. 	bool sufCmp(int i, int j)
  182. 	{
  183. 		if (pos[i] != pos[j])
  184. 			return pos[i] < pos[j];
  185. 		i += gap;
  186. 		j += gap;
  187. 		return (i < N && j < N) ? pos[i] < pos[j] : i > j;
  188. 	}
  189.  
  190. 	void buildSA()
  191. 	{
  192. 		N = S.size();
  193. 		for (int i{}; i < N; i++)
  194. 			SA[i] = i,
  195. 			pos[i] = S[i];
  196. 		for (gap = 1;; gap *= 2)
  197. 		{
  198. 			sort(SA, SA + N, sufCmp);
  199. 			for (int i{}; i < N - 1; i++)
  200. 				tmp[i + 1] = tmp[i] + sufCmp(SA[i], SA[i + 1]);
  201. 			for (int i{}; i < N; i++)
  202. 				pos[SA[i]] = tmp[i];
  203. 			if (tmp[N - 1] == N - 1)
  204. 				break;
  205. 		}
  206. 	}
  207.  
  208. 	void buildLCP()
  209. 	{
  210. 		for (int i = 0, k = 0; i < N; ++i)
  211. 		{
  212. 			if (pos[i] != N - 1)
  213. 			{
  214. 				for (int j = SA[pos[i] + 1]; S[i + k] == S[j + k];)
  215. 					++k;
  216. 				lcp[pos[i]] = k;
  217. 				if (k)
  218. 					--k;
  219. 			}
  220. 		}
  221. 	}
  222. }
  223. using namespace SuffixArray;
  224.  
  225. int countSubstrings(const HashRange &H, const Hash &s)
  226. {
  227. 	// A substring is a prefix of some suffix
  228. 	int last = S.length(), first = -1;
  229. 	// Upper bound
  230. 	{
  231. 		int L{}, R = S.length();
  232. 		while (L <= R)
  233. 		{
  234. 			int mid = ((L + R) >> 1);
  235. 			if (H.get(SA[mid], SA[mid] + s.size - 1) > s)
  236. 				last = mid, R = mid - 1;
  237. 			else
  238. 				L = mid + 1;
  239. 		}
  240. 	}
  241. 	// Lower bound
  242. 	{
  243. 		int L{}, R = S.length();
  244. 		while (L <= R)
  245. 		{
  246. 			int mid = ((L + R) >> 1);
  247. 			if (H.get(SA[mid], SA[mid] + s.size - 1) >= s)
  248. 				first = mid, R = mid - 1;
  249. 			else
  250. 				L = mid + 1;
  251. 		}
  252. 	}
  253. 	if (~first)
  254. 		return last - first;
  255. 	else
  256. 		return 0;
  257. }
  258.  
  259. int main()
  260. {
  261. 	ios_base::sync_with_stdio(false);
  262. 	cin.tie(nullptr);
  263. #ifndef ONLINE_JUDGE
  264. 	freopen("input.txt", "r", stdin);
  265. 	freopen("Output.txt", "w", stdout);
  266. #endif //! ONLINE_JUDGE
  267. 	int t = 1;
  268. 	ll N, Q;
  269. 	// cin >> t;
  270. 	while (t--)
  271. 	{
  272. 		cin >> N;
  273. 		vector<ll> P(N);
  274. 		for (int i{}; i < N; i++)
  275. 			cin >> P[i];
  276.  
  277. 		string suff("");
  278. 		for (int i = 1; i < N; i++)
  279. 		{
  280. 			if (P[i] > P[i - 1])
  281. 				suff += "U"; // Up
  282. 			else if (P[i] < P[i - 1])
  283. 				suff += "D"; // Down
  284. 			else
  285. 				suff += "C"; // Constant
  286. 		}
  287. 		S = suff;
  288. 		S += '#';
  289. 		buildSA(); // Suffix Array
  290. 		pre(2000001);
  291. 		HashRange StrHash = S;
  292. 		HashRange SuffHash = suff;
  293. 		cin >> Q;
  294. 		while (Q--)
  295. 		{
  296. 			int X;
  297. 			cin >> X;
  298. 			Hash cur = SuffHash.get(N - X, suff.length() - 1);
  299. 			cout << countSubstrings(StrHash, cur) << endl;
  300. 		}
  301. 	}
  302. 	return 0;
  303. }
Success #stdin #stdout #stderr 0.26s 40576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/OEbYTz
language:
R (R 3.5.2)
created:
28 days 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!