(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,

• Cows with $d_i=-1$ contribute $x_i$ to the multiset.
• Cows with $d_i=1$ contribute $L-x_i$ to the multiset.

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);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}

int N,L;
vi w,x,d;

void init() {
setIO("meetings");
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) {
W.pb(w[t]);
X.pb(x[t]);
D.pb(d[t]);
}
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]});
sort(all(v));
int tot = 0; trav(t,v) tot += t.s;
trav(t,v) {
tot -= 2*t.s;
if (tot <= 0) return t.f;
}
}

int main() {
init();
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