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"
#define ll long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int N = 4e5+5;
int cnt[N], arcalyk[4][N], tarhun[N][4];
ll pre[N], suf[N], cep[N], sag[N];
int wow(int a, int b){
return (!(a|b)?1:0);
}
vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
int n = (int)X.size();
for (int i = 0; i < n+n; i++)
cnt[i] = 0;
map<pii, int> mp;
for(int i = 1; i <= n; ++i)
mp[{1, i}] = X[i-1], mp[{i, 1}] = Y[i-1];
for(int i = 2; i <= n; ++i)
for(int j = 2; j <= 3; ++j)
mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);
for(int i = 2; i <= 3; ++i)
for(int j = 2; j <= n; ++j)
mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]);
int i = 3;
for(int j = 3; j <= n; ++j)
cnt[i-j+n] = mp[{i, j}];
int j = 3;
for(int i = 3; i <= n; ++i)
cnt[i-j+n] = mp[{i, j}];
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= n; j++)
arcalyk[i][j] = mp[{i,j}] + arcalyk[i][j-1];
for (int j = 1; j <= 3; j++)
for (int i = 1; i <= n; i++)
tarhun[i][j] = mp[{i,j}] + tarhun[i-1][j];
suf[n+n] = cep[n+n] = 0;
sag[0] = pre[0] = cnt[0];
for (int i = 1; i < n+n; i++){
pre[i] = pre[i-1] + cnt[i];
sag[i] = sag[i-1] + pre[i-1] + cnt[i];
}
for (int i = n+n-1; i >= 0; i--){
suf[i] = suf[i+1] + cnt[i];
cep[i] = cep[i+1] + suf[i+1] + cnt[i];
}
vector<ll> ans;
for(int i = 0; i < (int)L.size(); ++i){
int x = T[i]+1, y = L[i]+1, yy = R[i]+1, xx = B[i]+1;
ll res = 0;
while (x <= 3 and x <= xx)
res += arcalyk[x][yy]-arcalyk[x][y-1], x += 1;
if (x <= xx){
while (y <= 3 and y <= yy)
res += tarhun[xx][y]-tarhun[x-1][y], y += 1;
}
if (x <= xx and y <= yy){
int a = x-y+n, b = x-yy+n, k = xx-x+1;
swap(a, b);
int len = b-a+1;
b += k-1;
k = min(k, len);
res += cep[a] - (cep[a+k]+k*suf[a+k]);
res += sag[b] - (sag[b-k]+k*pre[b-k]);
a += k; b -= k;
if (a > b)
res -= cnt[++b] * 1LL * k;
res += (pre[b]-pre[a-1])*1LL*k;
}
ans.pb(res);
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |