Springboards USACO Gold 2020 January Contest

I was trying to solve Springboards, and I tried implementing a Segment Tree solution (as mentioned in the editorial). However, I am failing four test cases for some unknown reason. The test cases I’m failing are too large to debug, and any smaller case I make passes in my code.

The test cases I failed can be shown here:

My Solution

I essentially used the segment tree implementation on USACO Guide, and took segment tree minimums of y_1 after sorting the springboards by x-coordinates. However, since the y-coordinates are too large (10^9), I used coordinate compression and took segment tree minimums using the compressed y-coordinates.

My code here:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;

#define forn(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, a, b) for(ll i = a; i < b; i++)
#define rofn(i, n) for(ll i = n; i >= 0; i--)
#define ROF(i, a, b) for(ll i = a; i >= b; i--)
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))

typedef pair<pl, pl> SB;

template<class T> struct Seg { // comb(ID,b) = b
	const T ID = 1e18; T comb(T a, T b) { return min(a,b); }
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// min on interval [l, r]
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		return comb(ra,rb);

int main(){
	freopen("boards.in", "r", stdin);
	freopen("boards.out", "w", stdout);
	ll n, p; cin >> n >> p;
	vector<SB> boards;
	vl ycoords, dp(p + 1);
	forn(i, p){
		ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		boards.pb({{x1, y1}, {i, 1}});
		boards.pb({{x2, y2}, {i, -1}});
		ycoords.pb(y1), ycoords.pb(y2);
	boards.pb({{n, n}, {p, 1}});
	ycoords.pb(0), ycoords.pb(n);
	sor(ycoords); sor(boards);
	map<ll, ll> mp; ll cnt = 0;
	for(ll y: ycoords){
			mp[y] = ++cnt;
	Seg<ll> s; s.init(cnt);
	s.upd(mp[0] - 1, 0);
	for(SB board: boards){
		if(board.s.s == 1){
			dp[board.s.f] = s.query(mp[0] - 1, mp[board.f.s] - 1) + board.f.f + board.f.s;
		} else {
			s.upd(mp[board.f.s] - 1, dp[board.s.f] - board.f.f - board.f.s);
	cout << dp[p] << endl;

Can someone help identify why my code isn’t working?

Thanks in advance.

Considering that you are failing on one of the test cases with small P, I am surprised that you haven’t been able to generate a countercase.