Submission #2072099

---

Source Code Expand

#include <bits/stdc++.h>
//#include <math.h>
using namespace std;

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,P> PP;

//-----------------------------------------------------------------------------

int N,L;
int A[100000],B[100000],C[100000];
vector<P> flow,can;
ll ans;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin>>N>>L;
	REP(i,N) {
		cin>>A[i]>>B[i]>>C[i];
		if(B[i]-C[i]<0) can.pb(P(A[i],B[i]-C[i]));
		else if(B[i]-C[i]>0) flow.pb(P(A[i],B[i]-C[i]));
	}
	sort(ALL(can));sort(ALL(flow));

	REP(i,(int)flow.size()) {
		int v=flow[i].fi,num=flow[i].se;
		//cout<<"v,num "<<v<<' '<<num<<endl;
		while(num>0) {
			int idx=lower_bound(ALL(can),P(v,0))-can.begin();
			idx%=(int)can.size();
			int idx2;
			if(idx==0) idx2=can.size()-1;
			else idx2=idx-1;
			if(abs(can[idx].fi-v)>abs(can[idx2].fi-v)) swap(idx,idx2);
			int D=abs(can[idx].fi-v);
			D=min(D,L-D);
			if(can[idx].se+num>0) {
				ans+=can[idx].se*-1*D;
				num=num+can[idx].se;
				can.erase(can.begin()+idx);
			}
			else if(can[idx].se+num==0) {
				ans+=num*D;
				can.erase(can.begin()+idx);
				num=0;
			}
			else {
				ans+=num*D;
				can[idx].se+=num;
				num=0;
			}
			//cout<<"D "<<D<<endl;
		}
		//cout<<"v,ans "<<v<<' '<<ans<<endl;
	}
	//for(auto c:can) cout<<c.fi<<' '<<c.se<<endl;
	cout<<ans<<endl;


	return 0;
}

Submission Info

Judge Result