Subtask 1 (50%) :

• Duyệt trâu từ ~l~ đến ~r~ ,độ phức tạp ~O(N * Q)~.

Subtask 2 (50%) :

• Đầu tiên ta khởi tạo 4 mảng :

  • ~D[i]~ là khoảng cách thùng nước thứ ~i~ đến thùng nước thứ ~i + 1~ ~(D[n] = 0)~ .
  • ~SumW[i]~ là tổng các ~W[j]~ với ~(j > i)~.
  • ~SumD[i]~ là tổng các ~D[j]~ với ~(j > i)~.
  • ~SumWS[i]~ là tổng các ~W[j] * SumD[j]~ với ~(j > i)~.

Ta có công thức tính chi phí vận chuyển các thùng nước có chỉ số từ ~L~ đến ~R - 1~ về ~R~ là :

• ~sumWS[L] − sumWS[R]−sumD[R] ∗ (sumW[L] − sumW[R])~.

Code mẫu

#include <bits/stdc++.h>

#define fi first
#define se second
#define For(i, a, b) for (int i=a;i<=b;++i)
#define Ford(i, a, b) for(int i=a;i>=b;--i)

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef array<int, 3> arr;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

const int N = 1e6 + 5;

ll x[N], w[N], sw[N], sxw[N];

void solve()
{
    int n; cin >> n;
    For(i, 1, n) {
        cin >> x[i] >> w[i];
        sw[i] = sw[i - 1] + w[i];
        sxw[i] = sxw[i - 1] + x[i] * w[i];
    }
    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;

        assert(l <= r);
        r--;

        cout << x[r + 1] * (sw[r] - sw[l - 1]) - (sxw[r] - sxw[l - 1]) << "\n";
    }
}

int main()
{
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    solve();

    return 0;
}