Tavas and Karafs

题面翻译

问题描述 有无限个食品排成一排，其中第 i 个食品的体积 si 为 A + ( i - 1 ) * B 。 每一次，你最多可以同时吃 M 个食品，并使这 M 个食品的体积都减少 1 ，体积为 0 表示该食品被吃掉。

现在有 n 个询问，每个询问包含三个整数 L ， T ， M ，表示从第 L 个食品开始往右边吃，每次最多吃 M 个食品（ 可以是不连续的 M 个），最多吃 T 次，求一个最大的R ( L ≤ R ) ，使得第 L 个到第 R 个食品都被吃掉（必须是连续的）。

输入输出格式 输入格式 第一行，三个整数，A ， B ， n ( 1 ≤ A，B ≤ 10^6 ， 1 ≤ n ≤ 10^5 )

接下来 n 行，每行表示一个询问，包含三个整数 L ， T ， M ( 1 ≤ L ， T ， M ≤ 10^6 )

输出格式 输出共 n 行，每行一个整数，依次表示每个询问的 R ，无解则输出 −1 。 翻译由 @炼金法爷biu 提供

题目描述

Karafs is some kind of vegetable in shape of an $1×h$ rectangle. Tavaspolis people love Karafs and they use Karafs in almost any kind of food. Tavas, himself, is crazy about Karafs.

Each Karafs has a positive integer height. Tavas has an infinite 1-based sequence of Karafses. The height of the $i$ -th Karafs is $s_{i}=A+(i-1)×B$ .

For a given $m$ , let's define an $m$ -bite operation as decreasing the height of at most $m$ distinct not eaten Karafses by 1. Karafs is considered as eaten when its height becomes zero.

Now SaDDas asks you $n$ queries. In each query he gives you numbers $l$ , $t$ and $m$ and you should find the largest number $r$ such that $l<=r$ and sequence $s_{l},s_{l+1},...,s_{r}$ can be eaten by performing $m$ -bite no more than $t$ times or print -1 if there is no such number $r$ .

输入格式

The first line of input contains three integers $A$ , $B$ and $n$ ( $1<=A,B<=10^{6}$ , $1<=n<=10^{5}$ ).

Next $n$ lines contain information about queries. $i$ -th line contains integers $l,t,m$ ( $1<=l,t,m<=10^{6}$ ) for $i$ -th query.

输出格式

For each query, print its answer in a single line.

样例 #1

样例输入 #1

2 1 4
1 5 3
3 3 10
7 10 2
6 4 8

样例输出 #1

4
-1
8
-1

样例 #2

样例输入 #2

1 5 2
1 5 10
2 7 4

样例输出 #2

1
2