Two pointer - MUST DO, C++ (gcc)

Two pointer - MUST DO

const int mod = 1e9+7;

const int N = 5e5+5;
vector<int> cnt(N);

int foo (int l, int r, const vector<int>& v, const int B) {
    if (l == r) {
        if ((v[l] + v[r]) % B == (v[l] % B)) return 1;
        return 0;
    }
    int m = (l+r) >> 1;
    long long int ans = foo(l, m, v, B) + foo(m+1, r, v, B);
    
    int l1 = l, r1 = m, l2 = m+1, r2 = r;
    multiset<int> other;
    
    // MAX lies in LEFT
    int mx = 0;
    while (r1 >= l1) {
        mx = max(mx, v[r1]);
        
        while (l2 <= r2 && v[l2] <= mx) {
            cnt[v[l2] % B] ++;
            l2 ++;
        } 
        
        int req = (mx - v[r1]) % B;
        ans += cnt[req];
        
        r1 --;
    }
    for (int j = l; j <= r; j ++) cnt[v[j]%B] = 0;
    
    // MAX lies in RIGHT
    l1 = l, r1 = m, l2 = m+1, r2 = r;
    mx = 0;
    other.clear();
    
    while (l2 <= r2) {
        mx = max(mx, v[l2]);
        
        while (r1 >= l1 && v[r1] < mx) {
            cnt[v[r1] % B] ++;
            r1 --;
        }
        
        int req = (mx - v[l2]) % B;
        ans += cnt[req];
        
        l2 ++;
    }
    
    for (int j = l; j <= r; j ++) cnt[v[j]%B] = 0;
    
    return (ans % mod);
}

int Solution::solve(vector<int> &A, int B) {
    int n = A.size();

return foo(0, n-1, A, B);
}


run \| edit \| history \| help	0