abc181_b - Trapezoid Sum
31 Jan 2021 — Tags: math,easy — URLEach operation $a, b$, is equivalent to increasing the answer by $sq(b) - sq(a)$, where $sq(n)$ is the sum of the first $n$ natural numbers.
Time complexity: $O(n)$
Memory complexity: $O(1)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll sq(ll n) { return (n * (n + 1)) / 2; }
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
ll ans = 0;
for (int i = 0; i < n; ++i)
{
int a, b;
cin >> a >> b;
ans += sq(b) - sq(a - 1);
}
cout << ans << endl;
return 0;
}