Thanks a lot.

Can someone please help me with this, I have been trying to solve this question for hours. I don't understand why is it failing testcase 8 always. I don't know what i missed. My solution seems similar to the idea discussed in the edutorial. I have added comments to make it more clear. Any discussion would be helpful, Thanks.

~~~~~
#include<bits/stdc++.h>

#define lli long long int
#define MOD 998244353

using namespace std;

lli gcd(lli a, lli b);
lli binary_exp(lli a, lli b, lli mod);

priority_queue<lli, vector<lli>> MAX_HEAP;
priority_queue<lli, vector<lli>, greater<lli>> MIN_HEAP;

void solve(){
	lli n, m; cin >> n >> m;
	vector<tuple<lli, lli, lli, lli>> segment;
	for(int i=0;i<n;i++){
		lli l, r, p, q; cin >> l >> r >> p >> q;
		segment.push_back({r, l, p, q}); // note i put {r, l} rather than {l, r}
	}
	sort(segment.begin(), segment.end()); // sorting the segments based on r
	vector<lli> dp(m+1, 0); // dp[i] = probablity of filling 1 -> i exactly once with currently seen segments
	vector<lli> not_take(n, 0); // not_take[i] = prod of probablity of not taking segments 0 -> i
	dp[0] = 1; 
	for(int i=0;i<n;i++){
		auto seg = segment[i];
		lli l = get<1>(seg), r = get<0>(seg), p = get<2>(seg), q = get<3>(seg);
		lli not_p = ((q-p) * binary_exp(q, MOD-2, MOD))%MOD; // just getting the probablity of the segment not existing
		lli take_p = (p * binary_exp(q, MOD-2, MOD))%MOD;// probablity of segment existing
		if(i == 0){ // special case, first segment
			not_take[i] = not_p;
			dp[r] = take_p;
			continue;
		}
		// probablity of filling 1-> r if current segment doens't exist
		dp[r] = (dp[r]*not_p)%MOD; 
		not_take[i] = (not_p * not_take[i-1])%MOD; // updating not_take
		// exlude represents the probablity of not taking segments which overlap with the current segment.
		lli exclude = not_take[i-1];
		auto it = lower_bound(segment.begin(), segment.begin() + i, make_tuple(l, 0, 0, 0));
		if(it != segment.begin()){
			// 0 -> idx should index all the segment which do not overlap with the current segment
			int idx = distance(segment.begin(), it);idx--;
			// removing the probablity of non overlapping segment not existing
			exclude = (exclude * binary_exp(not_take[idx], MOD-2, MOD))%MOD;	
		}
		// updating dp[r]
		dp[r] = (dp[r] + (((take_p * exclude)%MOD)*dp[l-1])%MOD)%MOD;
	}
	cout << (dp[m]%MOD) << endl;
}

bool multitestcase = false;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int testCase = 1;
	if(multitestcase) cin >> testCase;
	while(testCase--){
		solve();
	}
	return 0;
}

lli gcd(lli a,lli b) {
	if(b == 0) return a;
	return gcd(b, a%b);
}

lli binary_exp(lli a, lli b, lli mod){
	lli res = 1;
	while(b > 0){
		if(b&1){
			res = (res*a)%mod;
		}
		a = (a*a)%mod;
		b = b/2;
	}
	return res;
}

~~~~~

which one?

Nice, that's a good solution. I got what you meant

Nice solution, I got what you meant.

How do you ensure all the all the vertex in the list are visited?

Thanks for the reply, Yes, we can solve it like that, But storing all the queries makes solving the problem in an offline way. I wanted to have an online solution which I believe is the way CSES problems are meant to be solved.

Thanks a lot, It was my first time hearing about that variation of segment tree and it's exactly the data structure I needed. Thanks again for the help

Hope what I meant was clear. One solution I was thinking was implement something similar to a ordered set from scratch, but i can't find any resource that might help me in same.

Thanks a lot for your reply. Yes, I thought of that, but it felt like cheating, cause the testcases are supposed to be processed in a online sense right. Rather than storing all the values of a[i], b[i], p[i], x[i] and then compressing them. What I mean is to compress the values of p[i], x[i] I need to know all the possible values which i might encounter during answering the queries, first then sort them and map them from 0, 1, 2... Or is there some other way to compress them in a online way?

found why it was wrong

Can someone please help me why my submission for problem E isn't working. I spent a lot of time but wasn't able to figure it out.

Can someone tell me what's wrong with my D1?

Solved it. nevermind

Thanks a lot for your help. I understood

Auto comment: topic has been updated by alyosha (previous revision, new revision, compare).

Thank you I will make change of '\n' to endl and cout.tie(NULL) in my codeforces template as well.

Hey thanks, it worked just right. I even remember your userName as I see it often in comments of contest editorials. Thanks a lot for the help.

I tried changing it to "\n" , it's still failing that one test case due to TLE, even when I run this code on my local device it takes 2 seconds. Something is definitely wrong in the code Just I can't figure it out.

Auto comment: topic has been updated by alyosha (previous revision, new revision, compare).

I am not sure if this as well is correct but, I was thinking it should be solved like , find all pairs with sum 10, remove those pairs, then find all pairs with sum 9 remove those pairs, ..... now if total number of pairs is less than the number of bags then false, else yes. If i am not wrong, you can find the number of pairs with a particular sum in O(n) so it shouldn't cost more than 1e4 per test Case overall.

This showed up in my online assessment too, I feel the testCases for this problem were quite weak cause what I did was sort the array in descending order and keep a bags array B. now for each element A[i] i try to find some bag by iterating B which A[i] can fit... if for any A[i] it can't fit then it's false, else true. This solution is definitely wrong but it passed all the testCases somehow.