| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1108797 | KasymK | Mosaic (IOI24_mosaic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 5005;
int v[N][N];
ll p[N][N], par[N];
vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
memset(v, -1, sizeof v);
int n = (int)X.size();
if(n >= N){
for(int i = 1; i <= n; ++i)
par[i] = par[i-1]+X[i-1];
int Q = (int)T.size();
vector<ll> ans;
for(int i = 0; i < Q; ++i)
ans.pb(R[i]+1-L[i]);
return ans;
}
for(int i = 1; i <= n; ++i)
par[i] = par[i-1]+X[i-1], v[1][i] = X[i-1];
for(int i = 1; i <= n; ++i)
v[i][1] = Y[i-1];
auto wow = [&](int a, int b) -> int {
return (!(a|b)?1:0);
};
auto sm = [&](int x, int x1, int y, int y1) -> ll {
return (p[x1][y1]+p[x-1][y-1]-p[x-1][y1]-p[x1][y-1]);
};
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(v[i][j]==-1 and ~v[i-1][j] and ~v[i][j-1])
v[i][j] = wow(v[i-1][j], v[i][j-1]);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
p[i][j] = p[i-1][j]+p[i][j-1]-p[i-1][j-1]+v[i][j];
int Q = (int)L.size();
vector<ll> ans;
for(int i = 0; i < Q; ++i)
ans.pb(sm(T[i]+1, B[i]+1, L[i]+1, R[i]+1));
return ans;
}
int main(){
freopen("file.txt", "r", stdin);
int n;
scanf("%d", &n);
vector<int> X, Y;
for(int i = 1; i <= n; ++i){
int x;
scanf("%d", &x);
X.pb(x);
}
for(int i = 1; i <= n; ++i){
int y;
scanf("%d", &y);
Y.pb(y);
}
int q;
scanf("%d", &q);
vector<int> T, B, L, R;
while(q--){
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
T.pb(a), B.pb(b), L.pb(c), R.pb(d);
}
vector<ll> ans = mosaic(X, Y, T, B, L, R);
for(auto i : ans)
printf("%lld ", i);
puts("");
return 0;
}