21 Days Training // Day (8 2/3)~(9 2/3)

C. Distance Indicators

This problems cost me much time. For about 20 minutes, I only had ideas about a O(n^2) algorithm, until I noticed this conclusion.

The pair (i, j) satisfies j – i = A_i + A_j .
But this condition is equalvent to A_i + i = j – A_j .
So, we can use a map to record the count of j that satisfies A_j + j = C .
Then, for each i, search for its A_i + i , add the count to ans.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;cin >> N;
    int A[N];
    for (int i=0;i<N;i++) cin >> A[i];
    map<int,int> det2;
    for (int i=0;i<N;i++) {
        if (det2.find(A[i]-i-1)==det2.end()) det2[A[i]-i-1]=0;
        det2[A[i]-i-1]++;
    }
    long long cnt=0;
    for (int i=0;i<N;i++) {
        if (det2.find(-(A[i]+i+1))==det2.end()) continue;
        cnt += det2[-(A[i]+i+1)] - (A[i]==0);
    }
    cout << cnt;
    return 0;
}

Note : The condition in Line 17 is useless.