| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1246498 | CyberCow | Mosaic (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> a[200005];
vector<ll> pref[200005];
ll n;
vector<ll> hart, hartpref, hartpp;
vector<ll> hartR, hartprefR, hartppR;
ll getachox(ll x, ll y)
{
if(x > y)return 0;
if(x == 0)return hartpp[y];
return hartpp[y] - hartpp[x - 1] - x * (hartpref[y] - hartpref[x - 1]);
}
ll getnvaz(ll x, ll y)
{
swap(x, y);
x = hartppR.size() - x - 1;
y = hartppR.size() - y - 1;
if(x > y)return 0;
if(x == 0)return hartppR[y];
return hartppR[y] - hartppR[x - 1] - x * (hartprefR[y] - hartprefR[x - 1]);
}
ll gumqaq(ll x, ll x1, ll y, ll y1)
{
if(x > x1)
{
swap(x, x1);
swap(y, y1);
}
if(y > y1)
{
swap(x, x1);
swap(y, y1);
}
ll arj = pref[x1][y1];
if(x)arj -= pref[x - 1][y1];
if(y)arj-=pref[x1][y - 1];
if(x && y)arj += pref[x - 1][y - 1];
return arj;
}
ll getzayobexa(ll x, ll y)
{
if(x > y)return 0;
if(x == 0)return hartpref[y];
return hartpref[y] - hartpref[x - 1];
}
ll gum(ll x, ll x1, ll y, ll y1)
{
if(x1 <= 2 || y1 <= 2)
{
return gumqaq(x, x1, y, y1);
}
ll qaq = 0;
if(y <= 0)
qaq += gum(x, x1, 0 ,0);
if(y <= 1 && 1 <= y1)
qaq += gum(x, x1, 1, 1);
y = max(y, 2);
if(x <= 0)
qaq += gum(0, 0, y, y1);
if(x <= 1 && 1 <= x1)
qaq += gum(1, 1, y, y1);
x = max(x, 2);
ll erk = y1 - y + 1;
ll qan = x1 - x + 1;
ll sksel = min(erk, qan);
swap(x, x1);
ll han = min(x - 2, y - 2);
x -= han;
y -= han;
han = min(x1 - 2, y1 - 2);
x1 -= han;
y1 -= han;
ll ind = a[x][y];
ll ind1 = a[x1][y1];
ll ans = 0;
ans += getachox(ind, ind + sksel - 2);
ans += getnvaz(ind1 - sksel + 2, ind1);
ans += getzayobexa(ind + sksel - 1, ind1 - sksel + 1) * sksel;
return ans + qaq;
}
vector<long long> mosaic(vector<ll> X, vector<ll> Y,
vector<ll> T, vector<ll> B,
vector<ll> L, vector<ll> R) {
ll Q = (ll)T.size();
vector<long long> C(Q, 0);
pref[0].push_back(X[0]);
a[0].push_back(X[0]);
for (ll i = 1; i < X.size(); i++)
{
a[0].push_back(X[i]);
pref[0].push_back(pref[0][i - 1] + a[0][i]);
}
for (ll i = 1; i < Y.size(); i++)
{
a[i].push_back(Y[i]);
pref[i].push_back(pref[i - 1][0] + a[i][0]);
}
ll n = X.size();
for (ll i = 1; i < n; i++)
{
for (ll j = 1; j < n; j++)
{
if(i <= 2 || j <= 2)
{
if(a[i - 1][j] == 0 && a[i][j - 1] == 0)
{
a[i].push_back(1);
}
else
{
a[i].push_back(0);
}
pref[i].push_back(pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + a[i][j]);
}
else
break;
}
}
if(X.size() <= 2)
{
for (ll i = 0; i < Q; i++)
{
C[i] = gum(T[i], B[i], L[i], R[i]);
}
return C;
}
for (ll i = X.size() - 1; i >= 2; i--)
{
hart.push_back(a[i][2]);
a[i][2] = hart.size() - 1;
}
for (ll i = 3; i < X.size(); i++)
{
hart.push_back(a[2][i]);
a[2][i] = hart.size() - 1;
}
hartpref.push_back(hart[0]);
for (ll i = 1; i < hart.size(); i++)
{
hartpref.push_back(hartpref[i - 1] + hart[i]);
}
hartpp.push_back(hart[0]);
for (ll i = 1; i < hartpref.size(); i++)
{
hartpp.push_back(hartpp[i - 1] + hart[i] * (i + 1));
}
hartR = hart;
reverse(hartR.begin(), hartR.end());
//
hartprefR.push_back(hartR[0]);
for (ll i = 1; i < hartR.size(); i++)
{
hartprefR.push_back(hartprefR[i - 1] + hartR[i]);
}
hartppR.push_back(hartR[0]);
for (ll i = 1; i < hartprefR.size(); i++)
{
hartppR.push_back(hartppR[i - 1] + hartR[i] * (i + 1));
}
//
for (ll i = 0; i < Q; i++)
{
C[i] = gum(T[i], B[i], L[i], R[i]);
}
return C;
}