CF1657D

发表于 分类于
For Gamers. By Gamers.

For Gamers. By Gamers.

Stop learning useless algorithm, go and solve some problems, try to learn how to use Binary Search!

场上三分瞎搞结果过了 Pretest，没多想结果被 Hack 了。。。于是 FST 了 QAQ。。。

很容易分析出来对于某个怪兽的某种单位所需要的花费：

$$ans=\min{c_i(1+\lfloor\dfrac{H_jD_j}{h_id_i}\rfloor)}$$

然后我就假装这玩意有单峰性质就瞎搞三分了。。。

实际上应该想到这个 $C$ 的范围只有 $10^6$，然后在上面 DP。。。

我们令 $f(x)$ 表示花费为 $x$ 的时候能够处理掉的最大的 $H_jD_j$ 应严格小于什么值。

然后处理多个单位的情况，显然有转移（调和级数 $O(n\log n)$）：

$$f(ij)=\max{f(ij),f(i)j}$$

然后用更高的价钱肯定包括更低价钱能处理的范围：

$$f(i)=\max{f(i),f(i-1)}$$

然后对于每个 $H_jD_j$，我们二分查找需要的价格即可。

感觉是很深必的题目，但我场上就是做不出来啊/kk。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}
inline void writes(ll x) {write(x);putchar(32);}

const ll N=1e6;

ll n,m,cc;
ll f[N+5];

int main() {

  n=read();cc=read();

  for(ll i=1;i<=n;i++) {
    ll c,d,h;
    c=read();d=read();h=read();
    f[c]=max(f[c],d*h);
  }

  for(ll i=1;i<=cc;i++) {
    for(ll j=1;j*i<=cc;j++) {
      f[i*j]=max(f[i*j],f[i]*j);
    }
    f[i]=max(f[i],f[i-1]);
  }

  m=read();

  for(ll i=1;i<=m;i++) {
    ll h,d;h=read();d=read();
    ll ans=lower_bound(f+1,f+cc+1,h*d+1)-f;
    if(ans>cc) writes(-1);
    else writes(ans);
  }

  return 0;
}