Untitled

mail@pastecode.io avatar
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