#include using namespace std; class WaveletMatrix{ public: WaveletMatrix(vector table) : table_origin(table){ long table_max = *max_element(table.begin(), table.end()); tablesize = table.size(); bitsize = 0; while(table_max){ bitsize++; table_max >>= 1; } assert(bitsize); matrix.resize(bitsize, vector(tablesize)); zero_count.resize(bitsize, vector(tablesize + 1, 0)); for(long i = 0; i < bitsize; i++){ for(long j = 0; j < tablesize; j++){ matrix[i][j] = (table[j] >> (bitsize - i - 1)) & 1; if(not matrix[i][j]) zero_count[i][j + 1]++; zero_count[i][j + 1] += zero_count[i][j]; } stable_sort(table.begin(), table.end(), [&](auto a, auto b){return ((a >> (bitsize - i - 1)) & 1) < ((b >> (bitsize - i - 1)) & 1);}); } table_sorted = table; } long kth_min(long l, long r, long k/*0-indexed*/){ long L = l; long R = r; for(long level = 0; level < bitsize; level++){ auto [Lcount0, Lcount1] = counts(0, L, level); auto [count0, count1] = counts(L, R, level); if(k < count0){ L = Lcount0; R = L + count0; }else{ L = zero_count[level][tablesize] + Lcount1; R = L + count1; k -= count0; } } return table_sorted[L]; } long range_freq(long l, long r, long lower, long upper){ //count i s.t. l <= i < r and lower <= table[i] < upper return range_freq(l, r, upper) - range_freq(l, r, lower); } private: vector> matrix; vector> zero_count;//count 0 in matrix[i][0, r) long tablesize; long bitsize; vector table_origin; vector table_sorted; pair counts(long l, long r, long level){ //{0の個数, 1の個数} in matrix[level][l, r)を返す return {zero_count[level][r] - zero_count[level][l], (r - zero_count[level][r]) - (l - zero_count[level][l])}; } long range_freq(long l, long r, long upper){ //count i s.t. l <= i < r and table[i] < upper if(upper >= (1 << bitsize)) return r - l; if(upper < 0) return 0; long res = 0; long L = l; long R = r; for(long level = 0; level < bitsize; level++){ auto [Lcount0, Lcount1] = counts(0, L, level); auto [count0, count1] = counts(L, R, level); if(((upper >> (bitsize - level - 1)) & 1) == 0){ //matrix[level][i] = 1 なら 必ず upper < table[i] L = Lcount0; R = L + count0; }else{ //matrix[level][i] = 0 なら 必ず table[i] < upper res += count0; L = zero_count[level][tablesize] + Lcount1; R = L + count1; } } return res; } }; int main(){ long res = 0; long N; cin >> N; vector A(N); for(long i = 0; i < N; i++) cin >> A[i]; for(auto &a : A) a += 1000000000; vector AminusL(N), AplusR(N); for(long i = 0; i < N; i++){ long L, R; cin >> L >> R; AminusL[i] = A[i] - L; AplusR[i] = A[i] + R; } WaveletMatrix wm(AminusL); for(long i = 0; i < N; i++){ auto d = distance(A.begin(), upper_bound(A.begin(), A.end(), AplusR[i])); res += wm.range_freq(i + 1, d, LONG_MIN, A[i] + 1); } cout << res << '\n'; }