#include <bits/stdc++.h>
#include "atcoder/segtree"
int op(int a, int b) {
return a + b;
}
int e() {
return 0;
}
using i64 = long long;
i64 c2(i64 x) {
return x * (x + 1) / 2;
}
void solve() {
int N, Q;
std::cin >> N >> Q;
std::vector<int> H(N), Y(Q);
for (auto &e : H) std::cin >> e;
for (auto &e : Y) std::cin >> e;
std::vector<std::pair<int, int>> queries(Q);
for (int i = 0; i < Q; ++i) queries[i] = {Y[i], i};
std::sort(queries.begin(), queries.end());
std::vector<std::pair<int, int>> mountains(N);
for (int i = 0; i < N; ++i) mountains[i] = {H[i], i};
std::sort(mountains.begin(), mountains.end());
atcoder::segtree<int, op, e> seg(N + 2);
seg.set(0, 1);
seg.set(N + 1, 1);
int j = 0;
for (int i = 0; i < N; ++i) seg.set(i + 1, 1);
std::vector<i64> answer(Q);
i64 countFlights = 0;
for (int i = 0; i < N; ++i) {
while (j != Q and queries[j].first < mountains[i].first) {
answer[queries[j].second] = countFlights;
++j;
}
const int m = mountains[i].second + 1;
const int r = seg.max_right(m + 1, [](int x) {
return x == 0;
});
const int l = seg.min_left(m, [](int x) {
return x == 0;
}) - 1;
seg.set(m, 0);
countFlights -= c2(r - m - 1);
countFlights -= c2(m - l - 1);
countFlights += c2(r - l - 1);
}
while (j != Q) {
answer[queries[j].second] = countFlights;
++j;
}
for (const auto e : answer) std::cout << e << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
}
Compilation message
pilot.cpp:3:10: fatal error: atcoder/segtree: No such file or directory
3 | #include "atcoder/segtree"
| ^~~~~~~~~~~~~~~~~
compilation terminated.
