#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=200050;
int x[N],y[N],a[N],b[N],rng[N];
int xl[N],xr[N],yl[N],yr[N];
inline int dist(int x1,int y1,int x2,int y2){return max(abs(x1-x2),abs(y1-y2));}
inline int get(int i,int X,int Y){return max((ll)0,a[i]-(ll)b[i]*dist(x[i],y[i],X,Y));}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int H,W,n,q;
cin>>H>>W>>n;
for(int i=1;i<=n;++i)cin>>x[i]>>y[i]>>a[i]>>b[i],rng[i]=a[i]/b[i];
cin>>q;
for(int i=1;i<=q;++i)cin>>xl[i]>>yl[i]>>xr[i]>>yr[i];
if(H>W){
swap(H,W);
for(int i=1;i<=n;++i)swap(x[i],y[i]);
for(int i=1;i<=q;++i)swap(xl[i],yl[i]),swap(xr[i],yr[i]);
}
vector<ll> fir(W+2,0),add(W+2,0),f_d(W+2,0),f_n(W+2,0),add_r(H+2,0);
vector<vector<ll>> cell(H,vector<ll>(W,0)),add_d1(H+2,vector<ll>(W+2,0)),add_d2(H+2,vector<ll>(W+2,0));
vector<vector<int>> work(H+1);
auto get_t=[&](int o,int i){return i<=x[o]?x[o]-i:i-x[o]-1;};
for(int i=1;i<=n;++i){
if(x[i]-rng[i]>0)work[x[i]-rng[i]].pb(i);
if(x[i]+rng[i]+1<=H)work[x[i]+rng[i]+1].pb(i);
if(rng[i]!=0){
int p=min(min(rng[i],x[i]),y[i]);
int q=min(min(rng[i]+1,H-x[i]+1),W-y[i]+1);
add_d1[x[i]-p+1][y[i]-p+1]+=b[i];
add_d1[x[i]+q][y[i]+q]-=b[i];
if(max(x[i]-rng[i]+1,1)<x[i]-p+1){
add_r[max(x[i]-rng[i]+1,1)]+=b[i];
add_r[x[i]-p+1]-=b[i];
}
p=min(min(rng[i]+1,x[i]+1),W-y[i]+1);
q=min(min(rng[i],H-x[i]),y[i]);
add_d2[x[i]-p+2][y[i]+p-1]-=b[i];
add_d2[x[i]+q+1][y[i]-q]+=b[i];
if(x[i]+q+1<min(x[i]+rng[i]+1,H+1)){
add_r[x[i]+q+1]-=b[i];
add_r[min(x[i]+rng[i]+2,H+1)]+=b[i];
}
}
if(x[i]<=rng[i]){
int t=get_t(i,0);
int val=get(i,0,y[i]);
if(y[i]-t-1>=1){
f_d[max(1,y[i]-rng[i])]+=b[i];
f_d[y[i]-t]-=b[i];
f_n[max(1,y[i]-rng[i])]+=val-(ll)(y[i]-t)*b[i];
f_n[y[i]-t]-=val-(ll)(y[i]-t)*b[i];
}
f_n[max(1,y[i]-t)]+=val;
f_n[min(W+1,y[i]+t+1)]-=val;
if(y[i]+t+1<=W){
f_d[y[i]+t+1]-=b[i];
f_d[min(W+1,y[i]+rng[i]+1)]+=b[i];
f_n[y[i]+t+1]+=val+(ll)(y[i]+t)*b[i];
f_n[min(W+1,y[i]+rng[i]+1)]-=val+(ll)(y[i]+t)*b[i];
}
}
}
for(int i=1;i<=W;i++){
f_n[i]+=f_n[i-1];
f_d[i]+=f_d[i-1];
fir[i]=f_n[i]+f_d[i]*i;
}
for(int i=1;i<=H;++i){
for(int o:work[i]){
int t=get_t(o,i);
if(t<=rng[o]){
int dif=t==rng[o]?get(o,i,y[o])-get(o,i-1,y[o]):(i<=x[o]?b[o]:-b[o]);
add[max(1,y[o]-t)]+=dif;
add[min(W+1,y[o]+t+1)]-=dif;
}
}
ll sum=0;
add_r[i]+=add_r[i-1];
add[1]+=add_r[i];
for(int j=1;j<=W;++j){
add_d1[i][j]+=add_d1[i-1][j-1];
add_d2[i][j]+=add_d2[i-1][j+1];
sum+=(add[j]+=add_d1[i][j]+add_d2[i][j]);
cell[i-1][j-1]=sum+fir[j];
cell[i-1][j-1]+=(i!=1?cell[i-2][j-1]:0)+(j!=1?cell[i-1][j-2]:0)-(i!=1&&j!=1?cell[i-2][j-2]:0);
}
}
for(int i=1;i<=q;++i){
ll ans=cell[xr[i]-1][yr[i]-1]-(xl[i]!=1?cell[xl[i]-2][yr[i]-1]:0)-(yl[i]!=1?cell[xr[i]-1][yl[i]-2]:0)+(xl[i]!=1&&yl[i]!=1?cell[xl[i]-2][yl[i]-2]:0);
ll sz=(xr[i]-xl[i]+1)*(yr[i]-yl[i]+1);
ll out=ans/sz;
if((ans%sz)*2>=sz)out++;
cout<<out<<"\n";
}
return 0;
}
Compilation message
nuclearia.cpp:3: warning: ignoring #pragma comment [-Wunknown-pragmas]
3 | #pragma comment(linker, "/stack:200000000")
|
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
209 ms |
235276 KB |
Output is correct |
2 |
Correct |
80 ms |
6648 KB |
Output is correct |
3 |
Correct |
78 ms |
6212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
178 ms |
235324 KB |
Output is correct |
2 |
Correct |
80 ms |
6556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
59512 KB |
Output is correct |
2 |
Incorrect |
76 ms |
6648 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
68004 KB |
Output is correct |
2 |
Correct |
79 ms |
6648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
298 ms |
242060 KB |
Output is correct |
2 |
Correct |
89 ms |
6904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
185 ms |
101348 KB |
Output is correct |
2 |
Correct |
83 ms |
6648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
174 ms |
66552 KB |
Output is correct |
2 |
Incorrect |
84 ms |
6904 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
184 ms |
66100 KB |
Output is correct |
2 |
Incorrect |
77 ms |
6648 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
438 ms |
246152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
447 ms |
246156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
308 ms |
72440 KB |
Output is correct |
2 |
Correct |
329 ms |
72828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
306 ms |
72696 KB |
Output is correct |
2 |
Correct |
302 ms |
78712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
274 ms |
72024 KB |
Output is correct |
2 |
Incorrect |
261 ms |
70392 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
269 ms |
70520 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |