GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Monday 17 October 2022

[Solution] Intersection and Union Codeforces Solution



F. Intersection and Union
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given n segments on the coordinate axis. The i-th segment is [li,ri]. Let's denote the set of all integer points belonging to the i-th segment as Si.

Let AB be the union of two sets A and BAB be the intersection of two sets A and B, and AB be the symmetric difference of A and B (a set which contains all elements of A and all elements of B, except for the ones that belong to both sets).

Let [op1,op2,,opn1] be an array where each element is either , or . Over all 3n1 ways to choose this array, calculate the sum of the following values:

|(((S1 op1 S2) op2 S3) op3 S4)  opn1 Sn|

In this expression, |S| denotes the size of the set S.

Input

The first line contains one integer n (2n3105).

Solution Click Below:-  ðŸ‘‰CLICK HERE👈
👇👇👇👇👇

Then, n lines follow. The i-th of them contains two integers li and ri (0liri3105).

Output

Print one integer — the sum of |(((S1 op1 S2) op2 S3) op3 S4)  opn1 Sn| over all possible ways to choose [op1,op2,,opn1]. Since the answer can be huge, print it modulo 998244353.


No comments:

Post a Comment