დროის ლიმიტი: 2 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: COCI, 2008/09, #5
მოცემულია N ცალი ყუთი ერთ რიგში, გადანომრილი 1_დან N_მდე. K იყოს მაქსიმალური რიცხვი, რომლისთვისაც K*K<=N. ყუთები დაყოფილია K ზომის ჯგუფებად (ბოლო ჯგუფი შესაძლოა უფრო პატარა ზომის იყოს). თითოეულ ჯგუფს აქვს თავისი შესაბამისი ჭიქა. სლავკო ყუთებზე აკეთებს შემდეგნაირ ოპერაციებს: ირჩევს ორ რიცხვს A და S, ყუთებში ნომრებით A, A+1, A+2, … , A+S-1 უნდა ჩაიდოს თითო ასანთის ღერი. თუმცა, თუ ოპერაციის დროს რომელიმე ჯგუფის თითოეულ ყუთში იდება ღერი, სლავკო ამის ნაცვლად ჯგუფის შესაბამის ჭიქაში ჩადებს 1 ღერს. თქვენი ამოცანაა თითოეული M ოპერაციისთვის დაადგინოთ რამდენი ღერის დამატება მოუწევს სლავკოს.
შესატანი მონაცემები:
პირველ ხაზზე N და M (1 <= N, M <= 100,000). შემდეგი M ცალი სტრიქონიდან თითოეულზე შემოდის S და A (1 <= A <= N, 1 <= A+S-1 <= N).
გამოსატანი მონაცემები:
M ცალ სტრიქონზე უნდა გამოიტანოთ თითო რიცხვი, i_ურ სტრიქონზე - i_ური ოპერაციისთვის საჭირო ასანთის ღერების რაოდენობა. პასუხში უნდა გაითვალისწინოთ წინა ოპერაციებზე იმ ჭიქაში ან ყუთში მოთავსებული ასანთის ღერების რაოდენობა, რომელშიც ასანთის ღერები მოცემული ოპერაციის დროს მოთავსდა.
შესატანი მონაცემები
11 3 6 5 3 1 11 1 დაკოპირება
გამოსატანი მონაცემები
4 1 6 დაკოპირება
შესატანი მონაცემები
16 3 2 2 12 3 6 11 დაკოპირება
გამოსატანი მონაცემები
2 7 3 დაკოპირება