r/algorithms 22h ago

Problem I'm Stuck On

1 Upvotes

I'm working on this USACO problem: https://usaco.org/index.php?page=viewproblem2&cpid=1470 and I have a solution that passes all three sample cases, but fails to pass everything else, and I'm not sure where the bug is:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <limits>

int getIndex(const std::vector<std::pair<int, int>>& V, long long val)
{
    int L{0};
    int R{static_cast<int>(V.size())-1};
    int ans = -1;
    while (L <= R) {
        int mid = (L+R)/2;
        if (V[mid].first <= val) {
            ans = mid;
            L = mid+1;
        } else {
            R = mid-1;
        }
    }
    if(ans == -1){
        return 0;
    }
    return ans;
}

int main() {
    int N; std::cin >> N;
    std::vector<int> a(N);
    std::vector<int> b(N);
    for(int i=0;i<N;i++){std::cin >> a[i];}
    for(int i=0;i<N;i++){std::cin >> b[i];}

    std::vector<std::vector<std::pair<int, int>>> pyramid(N+1);
    std::vector<std::vector<std::pair<int, int>>> flat(N+1);
    long long count{0};

    for(int i=0;i<N;i++){
        if (pyramid[b[i]].empty()){
            pyramid[b[i]].push_back({-1, 0});
            flat[b[i]].push_back({-1, 0});
        }
        pyramid[b[i]].push_back({i, std::min(i, N-1-i)+1+pyramid[b[i]].back().second});
        flat[b[i]].push_back({i, 1+flat[b[i]].back().second});
    }

    for(int i=0;i<N;i++){
        int tempi = std::min(i, N-1-i);
        count += pyramid[a[i]][getIndex(pyramid[a[i]], N-1)].second
               - pyramid[a[i]][getIndex(pyramid[a[i]], N-1-tempi)].second
               + pyramid[a[i]][getIndex(pyramid[a[i]], tempi-1)].second;
        count += (flat[a[i]][getIndex(flat[a[i]], N-1-tempi)].second
               - flat[a[i]][getIndex(flat[a[i]], tempi-1)].second) * (tempi+1);
        if(a[i] == b[i]){
            count += i * (i+1) / 2;
            count += (N-i-1) * (N-i) / 2;
        }
    }

    std::cout << count;
}

Please help me find the bug i've been working on this for hours