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){
if(!mp[y]){
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.