Submission #1026634

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 0x3fffffff;


int main(){
	//ios_base::sync_with_stdio(0);
	ll N, L, ans=1e18;
	ll a[200005], b[200005], c[200005];

	cin >> N >> L;
	rep(i,N) cin >> a[i] >> b[i] >> c[i];
	rep(i,N+2){
		a[i+N] = a[i] + L;
		b[i+N] = b[i];
		c[i+N] = c[i];
	}

	// ↓計算量を落とす前のコード。
	// numは累積和で表される。累積和の起点をソートして順に変化させることですべてのsumを効率よく計算する
//	rep(k,N){
//		ll num=0, sum=0;
//		rep(i,N){
//			ll len = a[k+i+1] - a[k+i];
//			num += b[k+i] - c[k+i];
//			sum += abs(num * len);
//		}
//		chmin(ans, sum);
//	}

	multimap<ll,ll> mp;
	double num = 0;	// 経路(a[i+1] a[i])を移動する人数
	rep(i,N){
		double len = a[i+1] - a[i];
		num += (b[i] - c[i]);
		mp.emplace( num, len );
	}

	ll bnum = mp.begin()->first;	// 前回のnum
	ll sum=0, sum_lenR = 0, sum_lenL = 0;	// 合計(ansの候補)、現在のnumより大きいほうにあるlenの合計、現在のnumより小さいほうにあるlenの合計
	for(auto p: mp){
		sum += abs( (p.first - bnum) * p.second );
		sum_lenR += p.second;
	}
	chmin(ans, sum);
	for(auto p: mp){
		ll d = p.first - bnum;
		bnum = p.first;
		sum += d * (sum_lenL - sum_lenR);
		chmin(ans, sum);
		sum_lenR -= p.second;
		sum_lenL += p.second;
	}

	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result