#include "mosaic.h"
#include <bits/stdc++.h>
#define ll long long
// #define endl "\n"
using namespace std;
const ll N = 2e5 + 5;
ll t[N];
void upd(ll i, ll d)
{
for (; i < N; i |= (i + 1)) t[i] += d;
}
ll sum(ll i)
{
ll ans = 0;
for (; i >= 0; i = (i & (i + 1)) - 1) ans += t[i];
return ans;
}
vector<ll> neg, pos, pneg, ppos;
map<ll, ll> mp[N];
map<ll, vector<pair<ll, ll>>> diag;
vector<array<ll, 3>> inc;
ll n, q;
void precomp()
{
for (ll i = 1; i < n; i++)
for (ll j = 1; j < n; j++)
{
if (i > 2 and j > 2) break;
mp[i][j] = !mp[i - 1][j] and !mp[i][j - 1];
diag[j - i].push_back(make_pair(i, j));
}
pos.push_back(0);
for (auto [x, v] : diag)
if (v.size() == 1)
{
if (mp[v[0].first][v[0].second])
inc.push_back({v[0].first, v[0].second, 1});
}
else
{
assert(v[0].first < v[1].first);
if (mp[v[0].first][v[0].second])
{
if (x < 0) neg.push_back(-x);
else pos.push_back(x);
}
else if (mp[v[1].first][v[1].second])
{
inc.push_back({v[0].first, v[0].second, -1});
if (x < 0) neg.push_back(-x);
else pos.push_back(x);
}
}
neg.push_back(0);
reverse(neg.begin(), neg.end());
// for (auto [a, b, c] : inc) cout << a << " " << b << " " << c << endl;
pneg.push_back(0);
ppos.push_back(0);
// cout << pos.size() << " " << neg.size() << endl;
// for (ll i : pos) cout << i << " ";
// cout << endl;
// for (ll i : neg) cout << i << " ";
// cout << endl;
for (ll i = 1; i < neg.size(); i++) pneg.push_back(pneg.back() + neg[i]);
for (ll i = 1; i < pos.size(); i++) ppos.push_back(ppos.back() + pos[i]);
sort(inc.begin(), inc.end());
}
ll sum(ll l, ll r, vector<ll> &pref)
{
r = min(r, (ll)pref.size() - 1);
l = max(0ll, l - 1);
return l >= r ? 0 : pref[r] - pref[l];
}
ll calc(ll i, ll j, vector<ll> &v, vector<ll> &pref)
{
if (j < 0 or i < 0) return 0;
ll l = upper_bound(v.begin() + 1, v.end(), j - i) - v.begin(), r = upper_bound(v.begin() + 1, v.end(), j) - v.begin();
return (l - 1) * i + j * (r - l) - sum(l, r - 1, pref);
// ll ans = (l - 1) * i + (r - l) * j;
// ans -= sum(l, r - 1, pref);
// return ans;
}
ll f(ll i, ll j)
{
return calc(i, j, pos, ppos) + calc(j, i, neg, pneg);
}
// i <= j - x -> x <= j - i
// i <= j - x -> i + x <= j -> x <= j - i
// i > j - x, +j * sz pref[]
// i <= j - x, then i > j - x (j - x might become less than 0, so need to keep track)
// max(i, j - x) -> x > 0
// max(i + x, j) -> x <= 0 (max(i, j - x), ij swapped, negative turned to positive)
vector<long long> mosaic(vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R)
{
n = X.size(), q = T.size();
for (ll i = 0; i < n; i++) mp[0][i] = X[i], mp[i][0] = Y[i];
for (ll i = 0; i < n; i++)
{
if (X[i])
inc.push_back({0, i, 1});
if (Y[i] and i) inc.push_back({i, 0, 1});
}
precomp();
array<ll, 3> qs[q << 2];
vector<ll> ans(q, 0);
// cout << "all good\n";
for (ll i = 0; i < q; i++)
{
qs[i * 4] = {T[i] - 1, L[i] - 1, i * 4};
qs[i * 4 + 1] = {B[i], R[i], i * 4 + 1};
qs[i * 4 + 2] = {T[i] - 1, R[i], i * 4 + 2};
qs[i * 4 + 3] = {B[i], L[i] - 1, i * 4 + 3};
}
sort(qs, qs + q * 4);
ll ptr = 0;
for (auto [x, y, ind] : qs)
{
ll id = (ind >> 2), tp = (ind & 3) < 2 ? 1 : -1;
while (ptr < inc.size() and inc[ptr][0] <= x) upd(inc[ptr][1], inc[ptr][2]), ptr++;
ans[id] += tp * (sum(y) + f(x, y));
}
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... |