(Analysis by Benjamin Qi)

Note: This problem is quite tricky for silver!

First, sort all the cows by $x$-coordinate. For partial credit, we can simulate each collision that the cows make in $O(N),$ for a worst-case runtime of $O(N^3).$

To make solving the problem in $O(N\log N)$ more manageable, let's split it into two independent parts.

Part 1: Determining $T.$

Consider the multiset of all times when the cows reach the barns. If the cows did not actually switch velocities,

Nevertheless, this multiset remains the same regardless of whether cows switch velocities or not.

Let $z$ be the number of cows with $d_i=-1.$ Then exactly $z$ cows reach the left barn, so these must be precisely the $z$ leftmost cows. Thus, we can just take all of the $x_i$ for the cows with initial $d_i=-1$ and set these equal to the finishing times of the $z$ leftmost cows. Similarly, we can just take all of the $L-x_i$ for cows with initial $d_i=1$ and set these equal to the finishing times of the $N-z$ rightmost cows. After this, we can sort all the finishing times again and maintain the current total weight in order to determine $T.$

Part 2: Determining the number of meetings.

Now we can ignore the weight condition and assume that cows do not switch velocities after meeting; essentially, they will pass through each other. This will not affect the answer. Then two cows with $x_i<x_j$ will meet if $d_i=1, d_j=-1, x_i+2T\ge x_j.$ The number of such pairs can be computed by iterating from left to right and maintaining a queue that consists of those cows with $d_i=1$ that you are currently considering as meeting candidates.

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

typedef long long ll;
typedef vector<int> vi; 
typedef vector<pair<int,int>> vpi; 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second

void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);

int N,L;
vi w,x,d;
void init() {
	cin >> N >> L;
	w.rsz(N), x.rsz(N), d.rsz(N);
	F0R(i,N) cin >> w[i] >> x[i] >> d[i];
	vi inds(N); iota(all(inds),0);
	sort(all(inds),[](int a, int b) { return x[a] < x[b]; });
	vi W,X,D;
	trav(t,inds) {
	swap(w,W), swap(x,X), swap(d,D);
int getTime() {
	vi lef, rig;
	F0R(i,N) {
		if (d[i] == -1) lef.pb(x[i]);
		else rig.pb(x[i]);
	vpi v;
	F0R(i,sz(lef)) v.pb({lef[i],w[i]});
	F0R(i,sz(rig)) v.pb({L-rig[i],w[sz(lef)+i]});
	int tot = 0; trav(t,v) tot += t.s;
	trav(t,v) {
		tot -= 2*t.s;
		if (tot <= 0) return t.f;
int main() {
	int t = getTime(); 
	queue<int> rig;
	int ans = 0;
	F0R(i,N) {
		if (d[i] == -1) {
			while (sz(rig) && rig.front()+2*t < x[i]) rig.pop();
			ans += sz(rig);
		} else rig.push(x[i]);
	cout << ans << "\n";

For some more problems in the same spirit see