粟粟的书架

Time Limit: 30 Sec Memory Limit: 552 MB

Description

幸福幼儿园 B29 班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢 Thomas H. Cormen 的文章。

粟粟家中有一个 R行C列 的巨型书架,书架的每一个位置都摆有一本书,上数第 i 行、左数第 j 列摆放的书有Pi,j页厚。

粟粟每天除了读书之外,还有一件必不可少的工作就是摘苹果,她每天必须摘取一个指定的苹果。

粟粟家果树上的苹果有的高、有的低,但无论如何凭粟粟自己的个头都难以摘到。

不过她发现, 如果在脚下放上几本书,就可以够着苹果;她同时注意到,对于第 i 天指定的那个苹果,只要她脚下放置书的总页数之和不低于Hi,就一定能够摘到。

由于书架内的书过多,父母担心粟粟一天内就把所有书看完而耽误了上幼儿园,于是每天只允许粟粟在一个特定区域内拿书。

这个区域是一个矩形,第 i 天给定区域的左上角是上数第 x1i 行的左数第 y1i 本书,右下角是上数第 x2i 行的左数第 y2i 本书。

换句话说,粟粟在这一天,只能在这﹙x2i-x1i+1﹚×﹙y2i-y1i+1﹚本书中挑选若干本垫在脚下,摘取苹果。

粟粟每次取书时都能及时放回原位,并且她的书架不会再撤下书目或换上新书,摘苹果的任务会一直持续M天。

给出每本书籍的页数和每天的区域限制及采摘要求,请你告诉粟粟,她每天至少拿取多少本书,就可以摘到当天指定的苹果。

Input

第一行是三个正整数R,C,M。

接下来是一个R行C列的矩阵,从上到下、从左向右依次给出了每本书的页数Pi,j。

接下来M行,第i行给出正整数x1i,y1i,x2i,y2i,Hi,表示第i天的指定区域是﹙x1i,y1i﹚与﹙x2i,y2i﹚间的矩形,总页数之和要求不低于Hi。

保证1≤x1i≤x2i≤R,1≤y1i≤y2i≤C。

Output

有M行,第i 行回答粟粟在第 i 天时为摘到苹果至少需要 拿取多少本书。如果即使取走所有书都无法摘到苹果,则在该行输出“Poor QLW” (不含引号)。

Sample Input

5 5 7
 14 15 9 26 53
 58 9 7 9 32
 38 46 26 43 38
 32 7 9 50 28
 8 41 9 7 17
 1 2 5 3 139
 3 1 5 5 399
 3 3 4 5 91
 4 1 4 1 33
 1 3 5 4 185
 3 3 4 3 23
 3 1 3 3 108

Sample Output

6
 15
 2
 Poor QLW
 9
 1
 3

HINT

对于 10%的数据,满足 R, C≤10;

对于 20%的数据,满足 R, C≤40;

对于 50%的数据,满足 R, C≤200,M≤200,000;

另有 50%的数据,满足 R=1,C≤500,000,M≤20,000;

对于 100%的数据,满足 1≤Pi,j≤1,000,1≤Hi≤2,000,000,000

Main idea

求给定矩阵(第二问是序列)中至少要取几个数加起来可以大于给定的值。

Solution

分为两部分实现:

第一部分n,m<=200,发现值<=1000,可以令tal表示到i,j位置为止的矩阵数值>=k的权值和与个数。每次二分最小值,判断是否可行,最后注意最小值不一定要取满。

第二部分为序列,用主席树求一段区间内>=某个值的权值和与个数,然后在主席树上二分,类似静态查询Kth,如果往左子树走则加上右子树的权值与个数,最后走到叶子节点的时候判断是否需要取满即可。

Code

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include<bits/stdc++.h>
using namespace std;

const int ONE=205;
const int TWO=5500005;
const int INF=1005;

int n,m,T;
int x,Need,cnt;
int res_num,res_value;
int a[ONE][ONE];
int X1,X2,Y1,Y2;

struct power
{
int root;
int left,right;
int value,num;
}Node[TWO];

struct point
{
int num;
int value;
}tal[ONE][ONE][INF];


int get()
{
int res,Q=1; char c;
while( (c=getchar())<48 || c>57)
if(c=='-')Q=-1;
if(Q) res=c-48;
while((c=getchar())>=48 && c<=57)
res=res*10+c-48;
return res*Q;
}

void Update(int &x,int y,int l,int r,int Val)
{
x=++cnt;
Node[x].value=Node[y].value+Val;
Node[x].num=Node[y].num+1;
Node[x].left=Node[y].left;
Node[x].right=Node[y].right;
if(l==r) return;
int mid=(l+r)/2;
if(Val<=mid) Update(Node[x].left,Node[y].left,l,mid,Val);
if(mid+1<=Val) Update(Node[x].right,Node[y].right,mid+1,r,Val);
}

void Query(int x,int y,int l,int r,int Need)
{
if(l==r)
{
if(Need && l)
{
int num=Need/l;
res_num+=num;
Need-=num*l;
if(Need>0) res_num++,Need-=l;
}
res_value=Need;
return;
}

int mid=(l+r)/2;
int value=Node[ Node[y].right ].value-Node[ Node[x].right ].value;
if(value > Need)
Query(Node[x].right,Node[y].right,mid+1,r,Need);
else
{
res_num+=Node[ Node[y].right ].num-Node[ Node[x].right ].num;
Query(Node[x].left,Node[y].left,l,mid,Need-value);
}
}


int Getvalue(int Val)
{
return tal[X2][Y2][Val].value + tal[X1-1][Y1-1][Val].value - tal[X1-1][Y2][Val].value - tal[X2][Y1-1][Val].value;
}

int Getnum(int Val)
{
return tal[X2][Y2][Val].num + tal[X1-1][Y1-1][Val].num - tal[X1-1][Y2][Val].num - tal[X2][Y1-1][Val].num;
}

void Deal(int ans)
{
res_num=Getnum(ans+1);
res_value=Getvalue(ans+1);
Need-=res_value;
if(Need>=0)
{
int num=Need/ans;
res_num+=num;
Need-=num*ans;
if(Need>0) res_num++,Need-=ans;
}
}


void PartOne()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
a[i][j]=get();
}

for(int k=0;k<=1000;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
tal[i][j][k].value=tal[i][j-1][k].value;
tal[i][j][k].num=tal[i][j-1][k].num;
if(a[i][j]>=k) tal[i][j][k].value+=a[i][j],tal[i][j][k].num++;
}

for(int j=1;j<=m;j++)
{
tal[i][j][k].value+=tal[i-1][j][k].value;
tal[i][j][k].num+=tal[i-1][j][k].num;
}
}
}


while(T--)
{
Need=0;
X1=get(); Y1=get(); X2=get(); Y2=get(); Need=get();
if(Getvalue(0)<Need)
{
printf("Poor QLW\n");
continue;
}
int l=0,r=1001;

int ans=1;
while(l<=r)
{
int mid=(l+r)/2;
if(Getvalue(mid)>Need)
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}

if(!ans) ans=1;
res_num=res_value=0;
Deal(ans);
printf("%d\n",res_num);
}
}

void PartTwo()
{
for(int i=1;i<=m;i++)
{
x=get();
Update(Node[i].root,Node[i-1].root,0,INF,x);
}

int x1,x2,y1,y2;
while(T--)
{
x1=get(); y1=get(); x2=get(); y2=get(); Need=get();
int l=0,r=1000;

res_num=res_value=0;
Query(Node[y1-1].root,Node[y2].root,0,INF,Need);
if(res_value>0) printf("Poor QLW\n");
else
printf("%d\n",res_num);
}
}

int main()
{
n=get(); m=get(); T=get();
if(n!=1) PartOne();
else PartTwo();
}