#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
#define int long long
using namespace std;
typedef long long ll;
typedef long double ld;
vector<vector<ll>> v,S1,S2;
int n,m,k,q;
int nradds=0;
void add(int x1,int y1,int x2,int y2,ll val)
{
x1=max(x1,1LL);
y1=max(y1,1LL);
x2=min(x2,n);
y2=min(y2,m);
v[x1][y1]+=val;
v[x2+1][y1]-=val;
v[x1][y2+1]-=val;
v[x2+1][y2+1]+=val;
}
ll getsum(int x1,int y1,int x2,int y2)
{
return v[x2][y2]-v[x1-1][y2]-v[x2][y1-1]+v[x1-1][y1-1];
}
ll put[2][2500005];
ll s[2500005];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k;
if(m==1)
{
for(int z=1;z<=k;z++)
{
ll x,y,a,b;
cin>>x>>y>>a>>b;
//assert(y==1);
ll nr=a/b;
put[0][x]+=a;
put[0][x+1]-=a;
ll st=x-nr;
ll dr=x-1;
if(dr>0)
{
st=max(st,1LL);
ll lg=dr-st+2;
put[0][st]+=a-lg*b;
put[0][dr+1]-=a-lg*b;
put[0][dr+1]-=(lg-1)*b;
put[1][st]+=b;
put[1][dr+1]-=b;
}
st=x+1;
dr=x+nr;
if(st<=n)
{
dr=min(dr,n*1LL);
ll lg=dr-st+2;
put[0][st]+=a;
put[0][dr+1]-=a;
put[0][dr+1]-=(lg-1)*(-b);
put[1][st]-=b;
put[1][dr+1]+=b;
}
}
ll suma=0;
for(int i=1;i<=n;i++)
{
suma+=put[0][i];
s[i]=suma;
}
ll si=0;
suma=0;
for(int i=1;i<=n;i++)
{
si+=put[1][i];
suma+=si;
s[i]+=suma;
}
for(int i=1;i<=n;i++)
s[i]+=s[i-1];
cin>>q;
while(q--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
//assert(y1==1&&y2==1);
ll val=s[x2]-s[x1-1];
ll rez=round(ld(val)/ld(x2-x1+1));
cout<<rez<<'\n';
}
return 0;
}
v.resize(n+10);
S1.resize(n+10);
S2.resize(n+10);
for(int i=0;i<=n+9;i++)
{
v[i].resize(m+10);
S1[i].resize(m+10);
S2[i].resize(m+10);
}
for(int z=1;z<=k;z++)
{
int x,y,a,b;
cin>>x>>y>>a>>b;
int nr=a;
int x1=x,y1=y,x2=x,y2=y;
int cnt=a/b;
if(a%b==0)
cnt--;
if(cnt==0)
{
add(x,y,x,y,a);
continue;
}
x1=x-cnt;
x2=x+cnt;
y1=y-cnt;
y2=y+cnt;
add(x1,y1,x2,y2,a);
add(x1,y1,x2,y2,-(cnt+1)*b);
/*while(x1<=x)
{
add(x1,y1,x2,y2,b);
x1++;
y1++;
x2--;
y2--;
}*/
S1[x1][y1]+=b;
S1[x+1][y+1]-=b;
S1[x+1][y+1]+=b;
S1[x2+2][y2+2]-=b;
if(y2+1<=m)
S2[x1][y2+1]-=b;
else
S2[x1+1][y2]-=b;
S2[x+1][y]+=b;
S2[x+1][y]-=b;
if(x2+2>n||y1-1<1)
continue;
S2[x2+2][y1-1]+=b;
}
for(int i=1;i<=n;i++)
{
ll x=i,y=1;
ll suma=0;
while(x<=n&&y<=m)
{
suma+=S1[x][y];
v[x][y]+=suma;
x++;
y++;
}
}
for(int j=2;j<=m;j++)
{
ll x=1,y=j;
ll suma=0;
while(x<=n&&y<=m)
{
suma+=S1[x][y];
v[x][y]+=suma;
x++;
y++;
}
}
for(int i=1;i<=n;i++)
{
ll x=i,y=m;
ll suma=0;
while(x<=n&&y>0)
{
suma+=S2[x][y];
v[x][y]+=suma;
x++;
y--;
}
}
for(int j=1;j<m;j++)
{
ll x=1,y=j;
ll suma=0;
while(x<=n&&y>0)
{
suma+=S2[x][y];
v[x][y]+=suma;
x++;
y--;
}
}
/*for(int i=1;i<=n;i++,cout<<'\n')
for(int j=1;j<=m;j++)
cout<<v[i][j]<<' ';*/
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1];
/*for(int i=1;i<=n;i++,cout<<'\n')
for(int j=1;j<=m;j++)
cout<<v[i][j]<<' ';*/
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
v[i][j]=v[i][j]+v[i-1][j]+v[i][j-1]-v[i-1][j-1];
//cout<<s[i][j]<<' ';
}
//assert(nradds<=k*max(n,m));
cin>>q;
while(q--)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
ll suma=getsum(x1,y1,x2,y2);
ll cells=(y2-y1+1)*(x2-x1+1);
ll rez=round(ld(suma)/ld(cells));
cout<<rez<<'\n';
}
return 0;
}
Compilation message
nuclearia.cpp: In function 'int main()':
nuclearia.cpp:108:13: warning: unused variable 'nr' [-Wunused-variable]
108 | int nr=a;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
20308 KB |
Output is correct |
| 2 |
Correct |
64 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
61 ms |
2344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
20436 KB |
Output is correct |
| 2 |
Correct |
63 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
123208 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
122 ms |
179552 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
22216 KB |
Output is correct |
| 2 |
Correct |
66 ms |
2888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
11780 KB |
Output is correct |
| 2 |
Correct |
64 ms |
2708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
77 ms |
122128 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
316 ms |
405164 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
201 ms |
61396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
231 ms |
61388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
296 ms |
62848 KB |
Output is correct |
| 2 |
Correct |
342 ms |
65568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
308 ms |
62332 KB |
Output is correct |
| 2 |
Correct |
302 ms |
69700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
132092 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
80 ms |
123308 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
