Untitled
unknown
plain_text
a month ago
2.1 kB
4
Indexable
Never
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; using ll = long long; template<class T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int dx[] = {0, 0, 1, -1, 1, 1, -1, -1}; int dy[] = {1, -1, 0, 0, 1, -1, 1, -1}; void File() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("errors.txt", "w", stderr); #else #endif } int main() { File(); int tt = 1; cin >> tt; for (int tc = 1; tc <= tt; tc++) { // a[i] <= a[i + 1] + x // a[i] - a[i + 1] <= x int n, q; cin >> n >> q; vector<ll> a(n); priority_queue<pair<int, int>> pq; for (int i = 0; i < n; ++i) { cin >> a[i]; if (i > 0) pq.emplace(a[i - 1] - a[i], i - 1); } vector<array<int, 2>> qu(q); for (int i = 0; i < q; ++i) cin >> qu[i][0], qu[i][1] = i; sort(qu.rbegin(), qu.rend()); // sort query such that (qu[i] > qu[i + 1]) set<int> notValid = {{-1, n - 1}}; ll cur = 1LL * n * (n - 1) / 2; vector<ll> ans(q); for (auto &[x, id]: qu) { while (!pq.empty() && pq.top().first > x) { int i = pq.top().second; pq.pop(); int R = *notValid.lower_bound(i), L = *(--notValid.lower_bound(i)); int lenAll = R - L, lenL = i - L, lenR = R - i; cur += (1LL * lenL * (lenL - 1) / 2) + (1LL * lenR * (lenR - 1) / 2) - (1LL * lenAll * (lenAll - 1) / 2); notValid.emplace(i); } ans[id] = cur; } for (auto &X: ans) cout << X << " "; cout << "\n"; } return 0; }
Leave a Comment