Library Checker problem from USACO Guide, Platinum

Debugging Help
#1

Library Checker

For this problem, my code is

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

template <class T>
void C(T a) { cout << a << '\n'; }

#define int long long 
#define mp make_pair
#define d(m,a,b) int m = (a + b) >> 1
#define ad(a, b) a = add(a, b)
#define chk(a, c, d) (a[0] == c && a[1] == d)
#define ci const int
#define M(a) (a % MOD)

ci maxn = 500000;
ci segn = (1<<20);
ci MOD = 998244353;

int add(int a, int b) { return (a + b) % MOD; }
int mult(int a, int b) { return (a * b) % MOD; }

int n, q;
int vals[maxn];

int seg[segn];
int flg[segn][2];

void form(int p) { seg[p] = add(seg[2*p], seg[2*p + 1]); }
void push(int p, int l, int r) {
	if (chk(flg[p], 0ll, 0ll)) return;
	if (l != r) {
		d(mid,l,r);
		seg[2*p] = add(mult(flg[p][0], seg[2*p]), mult(flg[p][1], mid - l + 1));
		seg[2*p + 1] = add(mult(flg[p][0], seg[2*p + 1]), mult(flg[p][1], r - mid));
		for (int i = 2*p; i < 2*p+2; i++) 
		  for (int j = 0; j < 2; j++)
			  ad(flg[i][j], flg[p][j]);
	}
	flg[p][0] = flg[p][1] = 0ll;
}

void bld(int p, int l, int r) {
	if (l == r) {
		seg[p] = vals[l];
		return;
	}
	d(mid,l,r);
	bld(2*p, l, mid); bld(2*p+1, mid+1, r);
	form(p);
}

void upd(int p, int l, int r, ci& L, ci& R, ci& b, ci& c) {
	if (r < L || R < l) return;
	if (L <= l && r <= R) {
		seg[p] = add(mult(b, seg[p]), mult(c, r - l + 1));
		ad(flg[p][0], b); ad(flg[p][1], c);
		return;
	}
	d(mid,l,r);
	upd(2*p, l, mid, L, R, b, c);
	upd(2*p+1, mid+1, r, L, R, b, c);
	form(p);
}

int qry(int p, int l, int r, ci& L, ci& R) {
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return seg[p];
	d(mid,l,r);
	return add(qry(2*p, l, mid, L, R), qry(2*p+1, mid+1, r, L, R));
}

signed main() {

	cin >> n >> q;
	for (int i = 0; i < n; i++) cin >> vals[i];

	bld(1, 0, n-1);

	for (int i = 0; i < q; i++) {
		int t; cin >> t;
		if (t == 0) {
			int l, r, b, c; cin >> l >> r >> b >> c; 
			upd(1, 0, n-1, l, r-1, b, c); 
		} else {
			int l, r; cin >> l >> r;
			C(qry(1, 0, n-1, l, r-1));
		}
	}

	return 0;
}

I am getting the sample test case correct, but most of the actual test cases. I don’t see where my implementation is wrong, and we have to take mod everywhere, but I don’t see anywhere I can add another mod…

Algorithm: Should be a pretty simple & direct lazy seg tree application.

The reason I think it is probably a mod-related error is because it passed two test cases labeled “small” and the sample test-case, but none of the test cases labeled max or random. Can someone please help me out? I’ve been debugging for hours without finding anything…

#2

Bump…

#3