Chefa tests Chef
All submissions for this problem are available.
Recently Chefa started doubting that Chef is cheating on her as he remains busy most of the time and barely spends time with her. He claims to be busy with his college studies. Chefa does not belive this
claim obviously. But to test if he is really busy learning, she wants to play a game with Chef.
Chefa has N boxes numbered 1 to N. The ith box contains Bi balls. Now Chefa gives an integer X to Chef. She will ask Chef Q queries which Chef has to answer correctly to prove that he is telling the truth. Help Chef in answering the queries.
See input format and example for clarification.
- The first line contains three space separated integers N and Q and X denoting the number of boxes, number of queries and the value of X respectively.
- The next line contains N space-separated integers the ith(1 <= i <= N) of which Bi is the number of balls in box i.
- Q lines follow. Each line contain a query.
There are two types of queries:-
- 1 l r Y - Add Y balls to each box between indices l and r (inclusive).
- 2 l r - Report the number of boxes between indices l and r (inclusive) in which the number of balls are exactly divisible by X.
For each query of type 2 l r, output a new line containing the answer to the corresponding query.
- 1 <= N, Q <= 105
- 1 <= X <= 10
- 0 <= Bi, Y <= 106
- 1 <= l <= r <= N
6 4 2 16 8 11 10 14 4 1 2 5 4 2 1 5 1 3 5 3 2 1 5
|Tags||encoding, horsbug98, horsbug98, lazypropagation, segment-tree|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions