Submission #171769

#	Time	Username	Problem	Language	Result	Execution time	Memory
171769		jangwonyoung	방벽 (JOI15_walls)	C++14	100 / 100	617 ms	80872 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 ansm,ansc;
ll ans[N];
void add(int l,int r,int x,int v){
	//cout << "!!! " << l << ' ' << r << ' ' << x << ' ' << v << endl;
	if(r==m+1) return;
	//cost of dudes in c[1,x] to move from l to r
	ansc+=1LL*v*(abs(p[r]-p[l]));
	if(sd[l]!=sd[r]) ansm-=v;
}
set<int>s;
ll mn[M],mx[M],dif[M];
ll mv(ll l,ll r){
	int pos=lower_bound(dif+1,dif+m+1,r-l+1)-dif;
	if(pos==m+1){
		return max(0LL,max(mx[m]-r,l-mn[m]));
	}
	ll res=0;
	if(l>mn[pos-1]){
		res+=l-mn[pos-1];r-=l-mn[pos-1];l-=l-mn[pos-1];
	}
	else if(r<mx[pos-1]){
		res+=mx[pos-1]-r;l+=mx[pos-1]-r;r+=mx[pos-1]-r;
	}
	if(l>mn[pos]){
		res+=l-mn[pos];r-=l-mn[pos];l-=l-mn[pos];
	}
	else if(r<mx[pos]){
		res+=mx[pos]-r;l+=mx[pos]-r;r+=mx[pos]-r;
	}
	return res;
}
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);mn[0]=1e9;mx[0]=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);
		mn[i]=min(mn[i-1],p[i]);
		mx[i]=max(mx[i-1],p[i]);
		dif[i]=mx[i]-mn[i];
	}
	s.insert(m+1);
	solve(1,0,n);
	for(int i=1; i<=m ;i++){
		ansc+=abs(p[i]-p[i-1]);
		if(sd[i]!=sd[i-1]) ansm--;
	}
	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);
		}
		//cout << ansm << ' ' << ansc << endl;
		ans[c[i].se]=ansm*c[i].fi+ansc;
	}
	for(int i=1; i<=n ;i++){
		ans[i]-=mv(0,b[i]);
		ans[i]+=mv(a[i],a[i]+b[i]);
	}
	for(int i=1; i<=n ;i++) cout << ans[i] << '\n';
}

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