oj.uz

Submission #171769

# Submission time Handle Problem Language Result Execution time Memory
171769 2019-12-30T10:50:54 Z jangwonyoung None (JOI15_walls) C++14
100 / 100
 617 ms 80872 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 18552 KB Output is correct
2 Correct 146 ms 39148 KB Output is correct
3 Correct 142 ms 39192 KB Output is correct
4 Correct 137 ms 39276 KB Output is correct
5 Correct 140 ms 39212 KB Output is correct
6 Correct 130 ms 39404 KB Output is correct
7 Correct 161 ms 38892 KB Output is correct
8 Correct 124 ms 38372 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 23416 KB Output is correct
2 Correct 384 ms 55172 KB Output is correct
3 Correct 171 ms 38520 KB Output is correct
4 Correct 575 ms 79340 KB Output is correct
5 Correct 593 ms 77528 KB Output is correct
6 Correct 600 ms 79328 KB Output is correct
7 Correct 577 ms 77676 KB Output is correct
8 Correct 573 ms 79248 KB Output is correct
9 Correct 276 ms 63652 KB Output is correct
10 Correct 379 ms 76780 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 18552 KB Output is correct
2 Correct 146 ms 39148 KB Output is correct
3 Correct 142 ms 39192 KB Output is correct
4 Correct 137 ms 39276 KB Output is correct
5 Correct 140 ms 39212 KB Output is correct
6 Correct 130 ms 39404 KB Output is correct
7 Correct 161 ms 38892 KB Output is correct
8 Correct 124 ms 38372 KB Output is correct
9 Correct 63 ms 23416 KB Output is correct
10 Correct 384 ms 55172 KB Output is correct
11 Correct 171 ms 38520 KB Output is correct
12 Correct 575 ms 79340 KB Output is correct
13 Correct 593 ms 77528 KB Output is correct
14 Correct 600 ms 79328 KB Output is correct
15 Correct 577 ms 77676 KB Output is correct
16 Correct 573 ms 79248 KB Output is correct
17 Correct 276 ms 63652 KB Output is correct
18 Correct 379 ms 76780 KB Output is correct
19 Correct 590 ms 78760 KB Output is correct
20 Correct 589 ms 79436 KB Output is correct
21 Correct 592 ms 79084 KB Output is correct
22 Correct 558 ms 75396 KB Output is correct
23 Correct 617 ms 79080 KB Output is correct
24 Correct 604 ms 80872 KB Output is correct
25 Correct 297 ms 65896 KB Output is correct
26 Correct 446 ms 77928 KB Output is correct
27 Correct 491 ms 79040 KB Output is correct