#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=2e5+5,M=2e5+5;
int n,m;
ll a[N],b[N];
pair<ll,int>c[N];
ll pc[N];
ll p[M];
bool sd[M];
vector<int>v[524288];
int prv[N];
vector<int>die[N];
void solve(int id,int l,int r){
if(l==r){
for(auto cur:v[id]) die[l+1].push_back(cur);
return;
}
int mid=(l+r+1)/2;
ll x=c[mid].fi;
ll xl=0,xr=x,xt=0;
for(auto cur:v[id]){
if(prv[cur]>xt){
if(sd[prv[cur]]){ xr=p[prv[cur]];xl=xr-x;xt=prv[cur];}
else{ xl=p[prv[cur]];xr=xl+x;xt=prv[cur];}
}
if(xr<p[cur] || xl>p[cur]){//important when x
v[id*2+1].push_back(cur);
if(xr<p[cur]){xr=p[cur],xl=xr-x,xt=cur;}
else {xl=p[cur],xr=xl+x,xt=cur;}
}
else{
v[id*2].push_back(cur);
prv[cur]=xt;
}
}
solve(id*2+1,mid,r);
solve(id*2,l,mid-1);
}
ll ans[M];
void add(int l,int r,int x,int v){
//cout << "!!! " << l << ' ' << r << ' ' << x << ' ' << v << endl;
if(x==0 || r==m+1) return;
//cost of dudes in c[1,x] to move from l to r
if(sd[l]==sd[r]) ans[r]+=1LL*v*x*abs(p[r]-p[l]);
else ans[r]+=1LL*v*(x*abs(p[r]-p[l])-(pc[x]));
}
set<int>s;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n >> m;
for(int i=1; i<=n ;i++){
cin >> a[i] >> b[i];
b[i]=b[i]-a[i];
c[i]={b[i],i};
}
sort(c+1,c+n+1);
for(int i=1; i<=n ;i++) pc[i]=pc[i-1]+c[i].fi;
s.insert(0);
for(int i=1; i<=m ;i++){
cin >> p[i];sd[i]=(p[i]>p[i-1]);
v[1].push_back(i);
s.insert(i);
}
s.insert(m+1);
solve(1,0,n);
for(int i=1; i<=n ;i++){
for(auto cur:die[i]){
auto it=s.lower_bound(cur);
auto it2=it;auto it3=it;
int l=*(--it2);int r=*(++it3);
add(l,cur,i-1,1);
add(cur,r,i-1,1);
add(l,r,i-1,-1);
s.erase(it);
}
}
for(auto it=s.begin(); it!=s.end() ;++it){
if(it==s.begin()) continue;
auto it2=it;--it2;
add(*it2,*it,n,1);
}
for(int i=1; i<=m ;i++) cout << ans[i] << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
23 ms |
18552 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
60 ms |
22732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
23 ms |
18552 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |