Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Linear Time Approach - O(n) time complexity
- long long countStableSubsegmentsLinear(const vector<long long>& capacity) {
- int n = capacity.size();
- long long count = 0;
- // Map to store endpoints with the same value
- // For each value v, we store indices where capacity[i] = v
- unordered_map<long long, vector<int>> valueToIndices;
- // Prefix sum for efficient sum calculation
- vector<long long> prefixSum(n + 1, 0);
- for (int i = 0; i < n; i++) {
- prefixSum[i + 1] = prefixSum[i] + capacity[i];
- valueToIndices[capacity[i]].push_back(i);
- }
- // For each possible value that could be at endpoints
- for (const auto& pair : valueToIndices) {
- long long value = pair.first;
- const vector<int>& indices = pair.second;
- // Check all pairs of indices where capacity[i] = value
- for (int i = 0; i < indices.size(); i++) {
- for (int j = i + 1; j < indices.size(); j++) {
- int l = indices[i];
- int r = indices[j];
- // Skip if the segment length is less than 3
- if (r - l < 2) continue;
- // Calculate sum between l+1 and r-1
- long long sumBetween = prefixSum[r] - prefixSum[l + 1];
- // Check if the subsegment is stable
- if (value == sumBetween) {
- count++;
- }
- }
- }
- }
- return count;
- }
- int main() {
- vector<long long> capacity = {9,3,1,2,3,9,10};
- long long result = countStableSubsegmentsLinear(capacity);
- cout << result << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
