302766: CF535C. Tavas and Karafs

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF535C/f71511a4daca20688928b2fd7edbe32cc3d94a45.png)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

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

输出样例 #1

4
-1
8
-1

输入样例 #2

1 5 2
1 5 10
2 7 4

输出样例 #2

1
2

Input

题意翻译

问题描述 有无限个食品排成一排,其中第 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 提供

加入题单

上一题 下一题 算法标签: