DCEPC11I - Impossible Boss
Vaibhav Sir and Saikat Sir, after completing their graduation, got a job together at a store.
Their boss at the store was Sidharth Sir, who was very strict and did not want anyone to have fun at the job. He gave Vaibhav and Saikat sir a very boring job of stacking columns of boxes in a row of size N.
To make it a little interesting, both of them decided that whenever they need to add more boxes, they will choose st and en, such that 1<=st<=en<=N, and place 1 box in column st, 2 boxes in column st+1, … and (en-st+1) boxes in column en.
When Sidharth sir saw this, he decided to have some fun of his own, and asked them to count the number of boxes in all columns from st to en, and tell him the result. Now Vaibhav and Saikat sir have come to you for help to answer the queries of their boss, as they do not want to lose their jobs.
Input
The first line contains N, the number of columns and Q, the number of queries.
The next Q lines can be of the following form –
1) 0 st en, meaning Vaibhav and Saikat sir add boxes to the columns from st to en as described above.
2) 1 st en, meaning Sidharth sir asks them to count the number of boxes in all columns from st to en.
Output
For all queries of type 2, output a line containing the answer to the query.
Example
Input: 5 6
0 2 4
1 1 5
0 1 5
0 3 5
1 1 5
1 3 5 Output: 6
27
23
Constraints
1<=N, Q<=100000
hide comments
Blitz:
2019-03-26 14:05:55
Nice problem , you should try it with sqrt |
|
DK...:
2019-03-24 12:18:38
Is interesting that treap or splay tree takes 2 times more than lazy st.
|
|
cohr3141592654:
2019-03-20 21:54:01
AC in one go
|
|
j1k7_7(JaskamalKainth):
2016-08-21 11:17:12
Easy Segment tree!! :) |
|
Pulkit Singhal:
2015-07-09 09:23:52
BIT Nailed It :) |
|
FoolForCS:
2014-10-27 20:20:03
For some reason take n as long long. That's all I changed in my code and got AC from previous int n. |
|
raghu ram:
2013-12-29 10:29:20
Nice Problem to solve.. :-) |
|
wisfaq:
2013-12-29 10:29:20
Why language restrictions?
|
Added by: | dce coders |
Date: | 2013-10-01 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ADA95 ASM32 ASM64 GAWK BASH BF CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO ICON ICK JS-RHINO LUA NEM NICE NODEJS OCAML PERL PERL6 PHP PIKE PRLG-swi RUBY SCALA SCM guile SCM qobi SED ST TCL WHITESPACE |
Resource: | Own Problem |