SPOJ.com - Problem MON2012

MON2012 - Monkey and apples

Monkey Chris loves apples. That's why he has planted lots of apple trees. He does two types of operations on this trees.

First operation "1 x y": means counting ripe apple trees on interval [x+c, y+c].
Second operation "2 x y": means that all apples on interval [x+c, y+c] get ripe(edible).

C=0 in the beginning and becomes the answer of each query ("1" operation).

Input

Input begins with M (1 <= M <= 10^5) the number of operations. Afterwards M lines each of them is an operation ("1" or "2"). 1<=X+C; Y+C<=10^9.

Example

Input
3
2 5 8
2 7 10
1 1 10

Output
6

Explanation

3 queries. Apples gets ripe on intervals 5-8 and 7-10. There are totally 6 ripe apple-trees on interval 1-10 so answer to query is 6.

Submit solution!

Added by:	Ikhaduri
Date:	2012-02-11
Time limit:	0.107s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ADA95 ASM32 ASM64 GAWK BASH BF C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO ICON ICK JS-RHINO LUA NEM NICE OCAML PAS-GPC PERL PERL6 PHP PIKE PRLG-swi SCALA SCM guile SCM qobi SED ST TCL
Resource:	izho 2012

hide comments



2019-04-28 13:22:15 DK... I got several TL's, It's necesary improve ur code for AC
2015-01-23 16:16:59 :( @$iddharth prasad the problem statement is simple u will be given a range update and a ragne query :D also if the same range is updated more than once donot add just leave it ;) Last edit: 2015-01-23 16:17:23
2015-01-20 13:39:40 rohith donot think too much a simple dynamic modification of segment tree :D
2013-08-30 18:27:06 $iddharth prasad someone plzz clarify the question
2012-04-05 15:25:46 :D Thanks for respond. So are you saying the ripe apples are left after picking? If that's the case, please underline this in the description or add an an example. Even so, there still seems to be problems with data on some files. I had issues reading value M, so I didn't have anything to do with the calculating. RE: in description it's said that operation 2 means COUNTING ripe apples, of course these apples stay ripe, we simply count them. RE RE: ok, my mistake. Even so you're still ignoring the issue with the input that I'm pretty sure is the cause of most of strange runtime errors. RE RE RE: I have no idea for the reason, but i have good news for you. Change language to C++ 4.0.0-8 and it will pass. ====== Okay... Thanks for that, but it's still the first time I've seen a behaviour like that. It looks like some file could be corrupt, unfinished or empty. Last edit: 2012-04-05 18:11:48
2012-04-05 15:25:46 :D It would be great if data check could be done here. It's hard to say here, because WA's can lead to this results, but I brute checked A LOT and extended the allowable data limits. There could be some issues with the file encoding or data itself on the 20-21 test case. I understand that it's official data, but I already seen cases of errors in official tournaments. UPDATE: There's seems to be something wrong right at the start. On reading number 'M'. You solution gave wrong answer on test: 6 2 1 7 2 10 12 1 7 11 2 11 13 1 8 10 1 15 17 the correct answers are 3 2 0 Last edit: 2012-03-31 08:50:23
2012-04-05 15:25:46 [Rampage] Blue.Mary I can't understand how my program caused RE(SIG). I've used assert and found (at least in my program) there's some test case(s) in which the given x<0, i.e. it doesn't meet the problem statement. Re:In task it says X+c>=1 not x>0. P.S it's impossible to construct such huge tree completely, you need to improve algorithm. P.P.S it's official constraints and official test data. Last edit: 2012-02-15 11:24:16
2012-04-05 15:25:46 Devil D what is the value of c in 'x+c' and 'y+c' in the beginning c=0.after each query("1" operation) c=answer to the query. Last edit: 2012-02-13 09:10:45