#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define NL "\n"
#define EL cout << NL
#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i >= 0; i--)
#define PRINTV(v) for (auto a: v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a: v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;
ll get(vvl& table, ll x, ll y) {
if (x >= 2 && y >= 2) return 0;
if (x < 0 || y < 0) return 0;
if (x >= (ll)table.size() || y >= (ll)table.size()) return 0;
return table[x][y];
}
void propagate(ll x, ll y, vvl& table) {
if (x == 0 || y == 0) return;
table[x][y] = !(get(table,x-1,y) || get(table,x,y-1));
}
std::vector<long long> mosaic(std::vector<int> x, std::vector<int> y, std::vector<int> t, std::vector<int> b, std::vector<int> l, std::vector<int> r) {
ll q = (int)t.size();
ll n = x.size();
if (n <= 2) {
vvl table(n,vl(n));
FOR(i,n) table[i][0] = x[i];
FOR(i,n) table[0][i] = y[i];
FORS(x,1,n) {
FORS(y,1,n) {
table[x][y] = !(table[x-1][y] || table[x][y-1]);
}
}
vl ans(q);
FOR(i,q) {
FORS(x,l[i],r[i]+1) {
FORS(y,t[i],b[i]+1) {
ans[i] += table[x][y];
}
}
}
return ans;
}
vvl table;
FOR(i,n) {
if (i <= 2) table.push_back(vl(n));
else table.push_back(vl(3));
}
FOR(i,n) table[i][0] = x[i];
FOR(i,n) table[0][i] = y[i];
FOR(i,n) propagate(1,i,table);
FOR(i,n) propagate(i,1,table);
FOR(i,n) propagate(i,2,table);
FOR(i,n) propagate(2,i,table);
vl diags(2*n-5);
FORS(i,2,n) {
diags[i-2+n-3] = table[i][2];
}
FORS(i,2,n) {
diags[2-i+n-3] = table[2][i];
}
vl dpsum(2*n-5);
ll sum = 0;
FOR(i,2*n-5) {
sum += diags[i];
dpsum[i] = sum;
}
vl dtsum(2*n-5);
vl drsum(2*n-5);
ll tsum = 0;
ll rsum = 0;
FOR(i,2*n-5) {
tsum += diags[i]*(i+1);
dtsum[i] = tsum;
}
FORR(i,2*n-5) {
rsum += diags[i]*(2*n-5-i);
drsum[i] = rsum;
}
vvl rectsum;
FOR(i,n) {
if (i <= 1) rectsum.push_back(vl(n));
else rectsum.push_back(vl(2));
}
FORR(y,n) {
ll maxx = 2;
if (y <= 1) maxx = n;
FORR(x,maxx) {
rectsum[x][y] = get(rectsum,x+1,y)+get(rectsum,x,y+1)-get(rectsum,x+1,y+1)+table[x][y];
}
}
vl res(q);
FOR(i,q) {
ll ans = 0;
if (!(b[i] >= 2 && r[i] >= 2)) {
ans = rectsum[l[i]][t[i]]-get(rectsum,r[i]+1,t[i])-get(rectsum,l[i],b[i]+1)+get(rectsum,r[i]+1,b[i]+1);
res[i] = ans;
continue;
}
if (t[i] <= 1 || l[i] <= 1) {
ans += rectsum[l[i]][t[i]];
}
if (t[i] <= 1 && r[i] < n-1) {
ans -= rectsum[r[i]+1][t[i]];
}
if (l[i] <= 1 && b[i] < n-1) {
ans -= rectsum[l[i]][b[i]+1];
}
ll x1 = max(2,l[i]);
ll y1 = max(2,t[i]);
ll x2 = r[i];
ll y2 = b[i];
if (x1 > x2 || y1 > y2) {
res[i] = ans;
continue;
}
ll left = x1-y2 +n-3;
ll right = x2-y1 +n-3;
ll w = min(abs(x2-x1),abs(y2-y1))+1;
if (w > 1) {
ans += dtsum[left+w-2]-left*dpsum[left+w-2];
if (left >= 1) {
ans -= dtsum[left]-left*dpsum[left];
}
ans += drsum[right-(w-2)]-(2*n-5-1-right)*dpsum[right];
if (right < 2*n-5-1) ans -= drsum[right+1];
if (right-(w-1) >= 0) ans += (2*n-5-1-right)*dpsum[right-(w-1)];
}
ans += w*dpsum[right-w+1];
if (left+w-1 > 0) ans -= w*dpsum[left+w-2];
res[i] = ans;
}
return res;
}
# | 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... |