#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, l[200200], r[200200];
ll ans[200200];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> l[i] >> r[i];
vector<int> p;
for(int i=1;i<=m;i++) {
int x; cin >> x;
if(!p.empty() && p.back() == x) continue;
if(p.size() > 1 && (p.rbegin()[1] < p.back()) == (p.back() < x)) p.pop_back();
p.push_back(x);
}
set<int> s;
for(int i=0;i<p.size();i++) s.insert(i);
priority_queue<array<int, 2>> pq;
for(int i=2;i+1<p.size();i++) pq.push({-abs(p[i]-p[i-1]), i});
vector<int> id(n); iota(id.begin(), id.end(), 1);
sort(id.begin(), id.end(), [&](auto a, auto b){ return r[a]-l[a] < r[b]-l[b]; });
ll sum = 0;
for(int i=2;i+1<p.size();i++) sum += abs(p[i]-p[i-1]);
for(int i : id) {
while(s.size() > 5 && !pq.empty() && -pq.top()[0] <= r[i]-l[i]) {
auto [c, u] = pq.top(); pq.pop();
auto it = s.lower_bound(u);
if(*it != u || abs(p[*it] - p[*prev(it)]) != -c) continue;
sum += c+c;
it = s.erase(s.erase(prev(it)));
if(prev(it) != s.begin() && next(it) != s.end()) {
auto C = abs(p[*it] - p[*prev(it)]);
pq.push({-C, *it});
}
}
if(s.size() <= 5) {
for(auto x : s) {
x = p[x];
if(x < l[i]) {
int K = l[i]-x;
l[i] -= K, r[i] -= K, ans[i] += K;
} else if(r[i] < x) {
int K = x-r[i];
l[i] += K, r[i] += K, ans[i] += K;
}
}
continue;
}
ans[i] = sum - 1ll*(r[i]-l[i])*(s.size()-3);
auto it = s.rbegin();
ans[i] += max(0, abs(p[*it] - p[*next(it)]) - (r[i]-l[i]));
int b = p[*s.begin()], nb = p[*next(s.begin())];
if(b < nb) {
if(b < l[i]) ans[i] += l[i]-b, r[i] -= l[i]-b;
if(r[i] < nb) ans[i] += nb-r[i];
else ans[i] += r[i]-nb;
} else {
if(r[i] < b) ans[i] += b-r[i], l[i] += b-r[i];
if(nb < l[i]) ans[i] += l[i]-nb;
else ans[i] += nb-l[i];
}
}
for(int i=1;i<=n;i++) cout << ans[i] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |