CodeChef is a non-commercial competitive programming community
Login
Username (New User? Signup) Password (Forgot Password?)
Signup
Login or
Signup with
Connect
Note
  • Publicize your achievements on your Facebook Wall.
  • Challenge your friends or ask them for help.

Site Navigation

  • PRACTICE
    • Easy
    • Medium
    • Hard
    • Challenge
    • Peer
  • COMPETE
    • All Contests
    • June Challenge 2013
    • May Cook-Off 2013
    • May Challenge 2013
  • DISCUSS
    • Forums
    • Blog
    • Wiki
    • Facebook
    • Twitter
  • COMMUNITY
    • Campus Chapters
    • Host your Contest
    • Go for Gold
    • All Educational Initiatives
  • HELP
    • Frequently Asked Questions
    • FAQ for problem setters
    • Problem Setting
    • Tutorials
    • Long Contest Ranks
    • Short Contest Ranks
    • Event Calendar
    • Top Contributors on Discuss
  • ABOUT
    • About CodeChef
    • Team CodeChef
    • Press Room
    • CodeChef Financials
    • CodeChef Sponsorships
    • CEO's Corner
    • Contact Us
    • About Directi
Home » Compete » April Long Contest » Gravel

Gravel

Problem code: SPREAD

  • All Submissions

All submissions for this problem are available.

Bob has n heap(s) of gravel (initially there are exactly c piece(s) in each). He wants to do m operation(s) with that heaps, each maybe:

  • adding pieces of gravel onto the heaps from u to v, exactly k pieces for each,
  • or querying "how many pieces of gravel are there in the heap p now?".

Request

Help Bob do operations of the second type.

Input

  • The first line contains the integers n,m,c, respectively.
  • m following lines, each forms:
    • S u v k to describe an operation of the first type.
    • Q p to describe an operation of the second type.

  • (Each integer on a same line, or between the characters S, Q and the integers is separated by at least one space character)

Output

For each operation of the second type, output (on a single line) an integer answering to the respective query (follows the respective Input order).

Example

Input:
7 5 0
Q 7
S 1 7 1
Q 3
S 1 3 1
Q 3
Output:
0
1
2

Limitations

  • 0<n≤106
  • 0<m≤250 000
  • 0<u≤v≤n
  • 0≤c,k≤109
  • 0<p≤n

Author: anhdq
Tester: rajivka
Editorial http://discuss.codechef.com/problems/SPREAD
Date Added: 5-05-2010
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, C, C99 strict, CLOJ, CPP 4.0.0-8, CPP 4.3.2, CS2, D, FORT, FS, GO, ICON, JAR, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PYTH, PYTH 3.1.2, RUBY, SCM guile, SCM qobi, ST, TCL


  • Submit

Comments

  • Login or Register to post a comment.

i am getting runtime error in

AnoopNarang @ 2 Apr 2011 01:40 AM

i am getting runtime error in c++ 4.3.2 and wrong answer in c++ 4.0.0.8 for same piece of code ... is it possible .. coz the basic syntax is same in both.

Why this problem is not

manoharsingh23 @ 2 Apr 2011 11:12 AM

Why this problem is not accepting solution with complexity of O(m*log(n))? Its showing TLE. Admin can you tell me reason.

Can there be more than one

santoshved @ 2 Apr 2011 11:13 AM

Can there be more than one space characters in between the input data?

Plz Ignore my above cmnt.

manoharsingh23 @ 2 Apr 2011 11:28 AM

Plz Ignore my above cmnt.

Can there be multiple spaces

nishit4091992 @ 2 Apr 2011 12:11 PM

Can there be multiple spaces or any other white space characters in the input...???

ok...got it..plz ignore my

nishit4091992 @ 2 Apr 2011 12:16 PM

ok...got it..plz ignore my above comment...

my same solution got accepted

Paresh Verma @ 2 Apr 2011 07:10 PM

my same solution got accepted in c++4.0.0.8 but am getting runtime error (sigsegv) in c++4.3.2!!!!!

Any ideas???

Getting TLE for a algo of

shankysodhi @ 3 Apr 2011 11:51 AM

Getting TLE for a algo of very low complexity . Anybody can tell plz why is it so ..... ???

You're getting TLE because

triplem @ 3 Apr 2011 11:57 AM

You're getting TLE because your program doesn't run within the time limit.

Now i m frustated by

gurpreet_09 @ 3 Apr 2011 08:18 PM

Now i m frustated by WA's....... :-x :(

first can be done in O(n) and

aayush123 @ 4 Apr 2011 06:56 PM

first can be done in O(n)

and second can be done in o(1)..

can sum1 explain the sample

gargankit @ 4 Apr 2011 10:53 PM

can sum1 explain the sample case?

got it ... plzz ignore my

gargankit @ 4 Apr 2011 10:57 PM

got it ...

plzz ignore my comment

Each integer on a same line,

ziyao_wei @ 5 Apr 2011 07:43 AM

Each integer on a same line, or between the characters S, Q and the integers is separated by at least one space character.

I'm not a native English speaker but I think there must be some grammar error here, since at least it should be 'intergers are', and I cannot seem to understand this sentence. Not mean to look for any hint here, but could anyone clarify or rephrase this to make this more understandable to non-native English speakers? Thanks a ton!

I dont understand why am I

switchcase @ 5 Apr 2011 02:41 PM

I dont understand why am I getting a TLE. I'm doing this in (mlogN) time and Im pretty sure there is no faster way to do it!!

Can someone plz explain how

sukhoi @ 5 Apr 2011 04:00 PM

Can someone plz explain how the input is terminating?? is it EOF or just a single input everytime the code is executed!!

Thank you.

does all the test cases need

tanzeel @ 5 Apr 2011 04:42 PM

does all the test cases need to be run within the time limit or is it for each test case??????

i am getting a runtime (NZEC

praveen97uma @ 6 Apr 2011 08:42 AM

i am getting a runtime (NZEC error) in Python. What does this error indicate and when does it usually occur?

Please help

There are lots of possible

acc1 @ 6 Apr 2011 10:47 AM

There are lots of possible reasons.

Segmentation fault , may be in ur case. (just a wild guess ;) )

Is answer in the range of c++

innocentdevil @ 6 Apr 2011 08:37 PM

Is answer in the range of c++ long??

There is only one test case

rajivka @ 6 Apr 2011 09:36 PM

There is only one test case per input file.

I have written a brute force

vikeshkhanna @ 7 Apr 2011 04:02 PM

I have written a brute force program, an optimized program, a random test-case case generator and a matcher. The matcher in C++  forks off child proceses to generate random test cases and runs both the versions and then matches their outputs. I have run 25,000 successful matches but my program (and that of a colleague) fails at around 4.30 seconds. I can see there have been a lot of correct submissions (which is why I was encouraged to write the generator and matcher). I hope the judge and test cases are alright.

I am getting always run time

bhogal08547 @ 8 Apr 2011 02:59 AM

I am getting always run time error i have test my code ideone.com where i am not getting runtime error please anybody help me.

@Admin: may i have one more

satya_patel @ 10 Apr 2011 01:24 PM

@Admin:

may i have one more test case please???

is ans in unsigned long range

rahul8iitkgp @ 10 Apr 2011 07:46 PM

is ans in unsigned long range or no bounds on ans ?

@Admin "output (on a single

rahul8iitkgp @ 10 Apr 2011 07:50 PM

@Admin

"output (on a single line) an integer answering to the respective query (follows the respective Input order)."

According to o/p specification it should be int . Admin please clarify.

@rahul, This mean

rajiv_adm @ 11 Apr 2011 09:17 PM

@rahul, This mean mathematical integer. The result can be as big as possible without any limit.

@Admin I am using Dev

prabhatcraz @ 13 Apr 2011 10:38 AM

@Admin

I am using Dev C++4.9.9.2

I was able to run my program correctly even for memory allocation of an integer array of size 250,000.

But I got runtime error, which usually happens for too large memory allocatoin(mostly).

Can you please suggest me the exact version of the compiler to use.(I know this is a weired question, but it would be really helpful).

 

@admin While trying to see

prabhatcraz @ 18 Apr 2011 02:06 PM

@admin

While trying to see all the submissions, next button doesn't work. is it a problem with my account only?

Due to this problem i cant see the successful codes if not present on that page

am getting runtime error ,

t1g0f8b8sgresu @ 6 Dec 2012 01:56 PM
am getting runtime error , can someone pls tell me what's the problem ?

SUCCESSFUL SUBMISSIONS


Fetching successful submissions

CodeChef is a non-commercial competitive programming community
  • About CodeChef
  • About Directi
  • CEO's Corner
  • C-Programming
  • Programming Languages
  • Contact Us
© 2009 Directi Group. All Rights Reserved. CodeChef uses SPOJ © by Sphere Research Labs
In order to report copyright violations of any kind, send in an email to copyright@codechef.com
CodeChef a product of Directi
The time now is:
CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month. We also aim to have training sessions and discussions related to algorithms, binary search, technicalities like array size and the likes. Apart from providing a platform for programming competitions, CodeChef also has various algorithm tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our programming contest judge accepts solutions in over 35+ programming languages. Preparing for coding contests were never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming challenges that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly coding contest and the shorter format Cook-off coding contest. Put yourself up for recognition and win great prizes. Our programming contests have prizes worth up to Rs.20,000 and $700lots more CodeChef goodies up for grabs.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be a part of CodeChef's Forums and interact with all our programmers - they love helping out other programmers and sharing their ideas. Have discussions around binary search, array size, branch-and-bound, Dijkstra's algorithm, Encryption algorithm and more by visiting the CodeChef Forums and Wiki section.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. You can also host a coding contest for your institute on CodeChef, organize an algorithm event and be a guest author on our blog.

Go For Gold

The Go for Gold Initiative was launched about a year after CodeChef was incepted, to help prepare Indian students for the ACM ICPC World Finals competition. In the run up to the ACM ICPC competition, the Go for Gold initiative uses CodeChef as a platform to train students for the ACM ICPC competition via multiple warm up contests. As an added incentive the Go for Gold initiative is also offering over Rs.8 lacs to the Indian team that beats the 29th position at the ACM ICPC world finals. Find out more about the Go for Gold and the ACM ICPC competition here.