diff options
| -rw-r--r-- | 2020/January/Gold/threesum.cpp | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/2020/January/Gold/threesum.cpp b/2020/January/Gold/threesum.cpp new file mode 100644 index 0000000..21e266c --- /dev/null +++ b/2020/January/Gold/threesum.cpp @@ -0,0 +1,40 @@ +#include <bits/stdc++.h> +#define f first +#define s second +using namespace std; +typedef long long ll; +typedef pair<int, int> ii; +constexpr int MAX = 1e6; + +int A[5005], cnt[5005] = { 0 }, M[2000002]; +ll ans[100001] = { 0 }; +vector<pair<ii, int>> q; + +int main() { + ifstream cin("threesum.in"); + ofstream cout("threesum.out"); + + int N, Q; cin >> N >> Q; + for (int i = 0; i < N; ++i) cin >> A[i]; + for (int i = 0; i < Q; ++i) { + int a, b; cin >> a >> b; + if (a != b) q.emplace_back(ii(--a, --b), i); + } + sort(begin(q), end(q), [](const pair<ii, int>& a, const pair<ii, int>& b) { + return a.f.s < b.f.s || (a.f.s == b.f.s && a.f.f > b.f.f); + }); + + auto it = begin(q); + for (int i = 0; i < N; ++i) { + ll sum = 0; + for (int j = i - 1; j >= 0; --j) { + int tmp = A[i] + A[j] + MAX; + if (tmp > 0 && tmp <= 2 * MAX && M[tmp]) cnt[j] += M[tmp]; + ++M[-A[j] + MAX]; + sum += cnt[j]; + while (it != end(q) && ii(j, i) == it->f) ans[(it++)->s] = sum; + } + for (int j = i - 1; j >= 0; --j) --M[-A[j] + MAX]; + } + for (int i = 0; i < Q; ++i) cout << ans[i] << '\n'; +} |