#binary search

Solutions This problem seem complicated if you try not using additional data structures. This is a typical case where pre-processing is needed and, in particular, we use two special kind of prefix sums. To answer to the first type of queries, we need to cache the running maximums of the prices: 1 2 3 4 5 6 7 8 vector<int> prefixMax(n); auto runningMax = p.front(); prefixMax[0] = runningMax; for (auto i=1; i<n; ++i) { prefixMax[i] = max(runningMax, p[i]); runningMax = prefixMax[i]; } In C++, we have a very useful standard algorithm to perform the same routine: [Read More]

Solutions

Solution

Solutions Consider this test case: Visually, for each element of B we should mark the elements in A and C that are less than or equal to that element: And, for 3: Performing the operation on the second 3 is redundant, because triplets must be unique. Along the way, we could multiply the count of A’s marked elements with the count of B’s marked elements. All the results will be then accumulated. [Read More]

Solutions A C++ solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 string s; cin >> s; int q, i; cin >> q; vector<int> w; char last = 0; for (auto c : s) { if (c == last) w.push_back(w.back()+c-'a'+1); else w.push_back(c-'a'+1); last = c; } sort(begin(w), end(w)); while (q--) { cin >> i; cout << (binary_search(begin(w), end(w), i) ? "Yes" : "No") << endl; } A C++ solution using std::set. [Read More]