글 읽기 - lowerbound랑 upperbound를 직접구현하면 틀렸답니다ㅜㅠ

wistlin47 2년 전 0

제가 구현한 lower boind랑 upperbound로 값을 찾을시 틀렸다고 뜹니다.... 저거를 그냥 라이브러리에 있는 lower upper을 쓰면 맞다고 뜨는거 보면 이진탐색 에 문제가 있느거 같은데 못찾겠어요ㅠㅠ

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
ll T,ans;
ll temp[1001];
vector<ll> A;
vector<ll> B;
int N,M;

void Input(){
    cin>>T;
    cin>>N;
    for(int i = 0; i<N; i++)   cin>>temp[i];
    
    for(int i = 0; i<N; i++){
        ll add = temp[i];
        A.push_back(add);
        for(int j = i+1; j<N; j++){
            add += temp[j];
            A.push_back(add);
        }
    }
    
    cin>>M;
    for(int i = 0; i<M; i++)    cin>>temp[i];
    
    for(int i = 0; i<M; i++){
        ll add = temp[i];
        B.push_back(add);
        for(int j = i+1; j<M; j++){
            add += temp[j];
            B.push_back(add);
        }
    }
}

int Lower_Bound(ll target){
    int start = 0;
    int end = B.size()-1;
    while(start < end){
        int middle = (start + end)/2;
        
        if(B[middle] < target) start = middle + 1;
        
        else end = middle;
    }
    return end;
}
int Upper_Bound(ll target){
    int start = 0;
    int end = B.size()-1;
    while(start < end){
        int middle = (start + end)/2;
        
        if(B[middle] <= target) start = middle + 1;
        else end = middle;
        
    }
    return end;
}

void Solve(){
    sort(B.begin(), B.end());
    
    for(int i = 0; i<A.size(); i++){
        ll target = T - A[i];
        //int idx1 = Lower_Bound(target);
        //int idx2 = Upper_Bound(target);
        int idx1 = lower_bound(B.begin(), B.end(), target) - B.begin();
        int idx2 = upper_bound(B.begin(), B.end(), target) - B.begin();

        ans += (idx2 - idx1);
    }
}

int main(){
    FAST;
    Input();
    Solve();
    cout<<ans<<'\n';
}