meetings.cpp

// Problem : Problem 2. Meetings
// Contest : USACO 2019 December Contest, Silver
// URL : http://usaco.org/index.php?page=viewproblem2&cpid=967
// Memory Limit : 256 MB
// Time Limit : 4000 ms
// Powered by CP Editor (https://github.com/coder3101/cp-editor)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;


typedef tuple<int, int, int> Cow;

bool Compare(const Cow& a, const Cow& b) {
    return get<0>(a) < get<0>(b);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef _DEBUG
    freopen("meetings.in", "r", stdin);
    freopen("meetings.out", "w", stdout);
    #endif
    int N, L;
    cin >> N >> L;
    vector<Cow> cows;
    int totw = 0;
    for (int i = 0; i < N; ++i) {
        int w, x, d;
        cin >> w >> x >> d;
        cows.emplace_back(x, w, d);
        totw += w;
    }
    int lo = 0, hi = L, mid, T = L+1;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        int numL = 0, numR = 0;
        for (auto& cow : cows) {
            int x = get<0>(cow);
            int d = get<2>(cow);
            if (d == -1 && x-mid <= 0) {
                ++numL;
            } else if (d == 1 && x+mid >= L) {
                ++numR;
            }
        }
        int sumw = 0;
        for (int i = 0; i < numL; ++i) {
            sumw += get<1>(cows[i]);
        }
        for (int i = N-1; i >= N-numR; --i) {
            sumw += get<1>(cows[i]);
        }
        if (2*sumw >= totw) {
            T = mid;
            hi = mid-1;
        } else {
            lo = mid+1;
        }
    }
    //cout << "T="<<T<<endl;
    ll ans = 0;
    // left to right
    sort(cows.begin(), cows.end(), Compare);
    int cnt = 0; // cnt to the left, going right
    int j = 0;
    for (int i = 0; i < N; ++i) {
        if (get<2>(cows[i]) == 1) {
            ++cnt;
            continue;
        }
        int minokx = get<0>(cows[i]) - 2*T;
        while (j < i && get<0>(cows[j]) < minokx) {
            if (get<2>(cows[j]) == 1) {
                --cnt;
            }
            ++j;
        }
        ans += cnt;
    }
    cnt = 0;
    j = N-1;
    for (int i = N-1; i >= 0; --i) {
        if (get<2>(cows[i]) == -1) {
            ++cnt;
            continue;
        }
        int maxokx = get<0>(cows[i]) + 2*T;
        while (j > i && get<0>(cows[j]) > maxokx) {
            if (get<2>(cows[j]) == -1) {
                --cnt;
            }
            --j;
        }
        ans += cnt;
    }
    ans /= 2;
    cout << ans << '\n';
}