Submission #171755

#	Time	Username	Problem	Language	Result	Execution time	Memory
171755		jangwonyoung	방벽 (JOI15_walls)	C++14	0 / 100	60 ms	22732 KiB

walls

#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';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 45
• Subtask 3: 0 / 45