fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. vector<int> numberOfItems(string s, vector<int> startIndices, vector<int> endIndices) {
  8.     int n = s.size();
  9.     vector<int> prefix(n, 0), leftPipe(n, -1), rightPipe(n, -1);
  10.     int count = 0, lastPipe = -1;
  11.  
  12.     // Step 1: Compute prefix sum of '*'
  13.     for (int i = 0; i < n; i++) {
  14.         if (s[i] == '|') lastPipe = i;
  15.         leftPipe[i] = lastPipe;
  16.         count += (s[i] == '*');
  17.         prefix[i] = count;
  18.     }
  19.  
  20.     lastPipe = -1;
  21.     for (int i = n - 1; i >= 0; i--) {
  22.         if (s[i] == '|') lastPipe = i;
  23.         rightPipe[i] = lastPipe;
  24.     }
  25. for (auto i : leftPipe) {
  26.     cout << i << " ";
  27. }
  28. cout << endl;
  29.  
  30. for (auto i : rightPipe) {
  31.     cout << i << " ";
  32. }
  33. cout << endl;
  34.  
  35.     // Step 2: Answer queries efficiently
  36.     vector<int> result;
  37.     for (size_t i = 0; i < startIndices.size(); i++) {
  38.         int left = startIndices[i] - 1; // Convert to 0-based index
  39.         int right = endIndices[i] - 1;
  40.  
  41.         int start = rightPipe[left];
  42.         int end = leftPipe[right];
  43.  
  44.         if (start != -1 && end != -1 && start < end) {
  45.             result.push_back(prefix[end] - prefix[start]);
  46.         } else {
  47.             result.push_back(0);
  48.         }
  49.     }
  50.  
  51.     return result;
  52. }
  53.  
  54. int main() {
  55.     string s = "|**|*|*";
  56.     vector<int> startIndices = {1, 1, 3, 5};
  57.     vector<int> endIndices = {5, 6, 6, 7};
  58.  
  59.     vector<int> res = numberOfItems(s, startIndices, endIndices);
  60.  
  61.     for (int x : res) {
  62.         cout << x << " ";
  63.     }
  64.  
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0 3 3 5 5 
0 3 3 3 5 5 -1 
2 3 1 0
https://ideone.com/keJIWV
language:
C++ (gcc 8.3)
created:
1 day 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!