# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1142957 | ag_1204 | Mosaic (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define si set<int>
#define pb push_back
void solve() {
int n; cin>>n;
int grid[n+1][n+1],cnt[n+1][n+1];
memset(cnt,0,sizeof(cnt));
for (int i=1;i<=n;i++) {
int x; cin>>x; grid[1][i]=x;
cnt[1][i]=cnt[1][i-1]+x;
}
for (int i=1;i<=n;i++) {
int y; cin>>y; grid[i][1]=y;
cnt[i][1]=cnt[i-1][1]+y;
}
for (int i=2;i<=n;i++) {
for (int j=2;j<=n;j++) {
if (grid[i][j-1]+grid[i-1][j]>0) grid[i][j]=0;
else grid[i][j]=1;
cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+grid[i][j];
}
}
/*
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) cout<<grid[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) cout<<cnt[i][j]<<" ";
cout<<endl;
}
*/
int q; cin>>q;
while(q--) {
int a,b,c,d; cin>>a>>b>>c>>d; b++; d++;
cout<<cnt[b][d]+cnt[a][c]-cnt[a][d]-cnt[b][c]<<endl;
}
return;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int tt=1; //cin>>tt;
while(tt--) {
solve();
}
return 0;
}