GUPTA MECHANICAL

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

Thursday 8 September 2022

[Solution] Illumination Codeforces Solution | Solution Codeforces


G. Illumination
time limit per test
8 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Consider a segment [0,d] of the coordinate line. There are n lanterns and m points of interest in this segment.

For each lantern, you can choose its power — an integer between 0 and d (inclusive). A lantern with coordinate x illuminates the point of interest with coordinate y if |xy| is less than or equal to the power of the lantern.

A way to choose the power values for all lanterns is considered valid if every point of interest is illuminated by at least one lantern.

You have to process q queries. Each query is represented by one integer fi. To answer the i-th query, you have to:

  • add a lantern on coordinate fi;
  • calculate the number of valid ways to assign power values to all lanterns, and print it modulo 998244353;
  • remove the lantern you just added.
Input

The first line contains three integers dn and m (4d31051n21051m18) — the size of the segment, the number of lanterns and the number of points of interest, respectively.

The second line contains n integers l1,l2,,ln (1lid1), where li is the coordinate of the i-th lantern.

Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

The third line contains m integers p1,p2,,pm (1pid1), where pi is the coordinate of the i-th point of interest.

The fourth line contains one integer q (1q5105) — the number of queries.

The fifth line contains q integers f1,f2,,fq (1fid1), where fi is the integer representing the i-th query.

Additional constraint on the input: during the processing of each query, no coordinate contains more than one object (i. e. there cannot be two or more lanterns with the same coordinate, two or more points of interest with the same coordinate, or a lantern and a point of interest with the same coordinate).

Output

For each query, print one integer — the answer to it, taken modulo 998244353.

No comments:

Post a Comment