| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1124239 | Mousa_Aboubaker | 모자이크 (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> mosaic(vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R)
{
vector<int> x = X, y = Y, t = T, b = B, l = L, r = R;
int n = (int)x.size(), q = (int)t.size();
if(n <= 5000)
{
vector a(n, vector<int>(n));
for(int i = 0; i < n; i++)
{
a[0][i] = x[i];
a[i][0] = y[i];
}
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
a[i][j] = a[i - 1][j] == 0 and a[i][j - 1] == 0;
vector pref(n + 1, vector<int>(n + 1));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
pref[i + 1][j + 1] = pref[i + 1][j] + pref[i][j + 1] - pref[i][j] + a[i][j];
}
}
vector<long long> res(q);
for(int i = 0; i < q; i++)
{
int i1 = t[i], j1 = l[i];
int i2 = b[i], j2 = r[i];
res[i] = pref[i2 + 1][j2 + 1] - pref[i1][j2 + 1] - pref[i2 + 1][j1] + pref[i1][j1];
}
return res;
}
vector<int> x2(n - 1), y2(n - 1);
x2[0] = x[1] == 0 and y[1] == 0;
for(int i = 2; i < n; i++)
{
x2[i - 1] = x[i] == 0 and x2[i - 2] == 0;
}
y2[0] = x2[0];
for(int i = 2; i < n; i++)
{
y2[i - 1] = y[i] == 0 and y2[i - 2] == 0;
}
vector<int> x3(n - 2), y3(n - 2);
x3[0] = x2[1] == 0 and y2[1] == 0;
for(int i = 2; i < n - 1; i++)
{
x3[i - 1] = x2[i] == 0 and x3[i - 2] == 0;
}
y3[0] = x2[1] == 0 and y2[1] == 0;
for(int i = 2; i < n - 1; i++)
{
y3[i - 1] = y2[i] == 0 and y2[i - 2] == 0;
}
vector<long long> pref1x(n), pref1y(n);
for(int i = 0; i < n; i++)
{
if(i)
{
pref1x[i] = pref1x[i - 1];
pref1y[i] = pref1y[i - 1];
}
pref1x[i] += x[i];
pref1y[i] += y[i];
}
vector<long long> pref2x(n - 1), pref2y(n - 1);
for(int i = 0; i < n - 1; i++)
{
if(i)
{
pref2x[i] = pref2x[i - 1];
pref2y[i] = pref2y[i - 1];
}
pref2x[i] += x2[i];
pref2y[i] += y2[i];
}
vector<long long> pref3x(n - 2), pref3y(n - 2);
for(int i = 0; i < n - 2; i++)
{
if(i)
{
pref3x[i] = pref3x[i - 1];
pref3y[i] = pref3y[i - 1];
}
pref3x[i] += x3[i];
pref3y[i] += y3[i];
}
vector<long long> res(q, 0);
for(int i = 0; i < q; i++)
{
int i1 = t[i], i2 = b[i];
int j1 = l[i], j2 = r[i];
if(i1 == 0)
{
res[i] = pref1x[j2] - (j1 == 0 ? 0 : pref1[j1 - 1]);
continue;
}
if(i1 == 1)
{
if(j1 == 0)
{
res[i] = y[1];
if(j2 != j1)
{
res[i] += pref2x[j2 - 1];
}
}
else
{
res[i] = pref2x[j2 - 1] - (j1 - 1 == 0 ? 0 : pref2x[j1 - 2]);
}
continue;
}
if(j2 == 0)
{
res[i] = y[i1];
continue;
}
if(j2 == 1)
{
res[i] = y2[i1 - 1];
if(j1 == 0)
res[i] += y[i1];
continue;
}
if(j1 == 0)
{
res[i] += y[i1];
j1++;
}
if(j1 == 1)
{
res[i] += y2[i1 - 1];
j1++;
}
if(i1 < j2)
{
res[i] += pref3x[j2 - i1];
if(i1 < j1)
{
res[i] -= (j1 - i1 == 0 ? 0 : pref3x[j1 - i1 - 1]);
}
else
{
res[i] += pref3y[i1 - j1];
}
}
else
{
res[i] += pref3y[i1 - j2];
if(i1 >= j1)
{
res[i] -= (i1 - j1 == 0 ? 0 : pref3y[i1 - j1 - 1]);
}
else
{
res[i] += pref3x[j1 - i1];
}
}
}
return res;
}