| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 144293 | SamAnd | UFO (IZhO14_ufo) | C++17 | 1437 ms | 255608 KiB |
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>
using namespace std;
void sar(int**& a, int n, int m)
{
a = new int*[n + 5];
for (int i = 0; i < n + 5; ++i)
a[i] = new int[m + 5];
for (int i = 0; i < n + 5; ++i)
for (int j = 0; j < m + 5; ++j)
a[i][j] = 0;
}
int n, m, r, q, k;
int** a;
int** tt, **ts;
void bil(int*& a, int*& t, int tl, int tr, int pos)
{
if (tl == tr)
{
t[pos] = a[tl];
return;
}
int m = (tl + tr) / 2;
bil(a, t, tl, m, pos * 2);
bil(a, t, m + 1, tr, pos * 2 + 1);
t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}
vector<int> v;
void qryl(int*& t, int tl, int tr, int x, int pos)
{
if (tl == tr)
{
v.push_back(tl);
return;
}
int m = (tl + tr) / 2;
if (t[pos * 2] >= x)
qryl(t, tl, m, x, pos * 2);
if (v.size() > r)
return;
if (t[pos * 2 + 1] >= x)
qryl(t, m + 1, tr, x, pos * 2 + 1);
}
void qryr(int*& t, int tl, int tr, int x, int pos)
{
if (tl == tr)
{
v.push_back(tl);
return;
}
int m = (tl + tr) / 2;
if (t[pos * 2 + 1] >= x)
qryr(t, m + 1, tr, x, pos * 2 + 1);
if (v.size() > r)
return;
if (t[pos * 2] >= x)
qryr(t, tl, m, x, pos * 2);
}
int qry(int*& t, int tl, int tr, int x, int pos)
{
if (tl == tr)
return t[pos];
int m = (tl + tr) / 2;
if (x <= m)
return qry(t, tl, m, x, pos * 2);
else
return qry(t, m + 1, tr, x, pos * 2 + 1);
}
void ubd(int*& t, int tl, int tr, int x, int pos)
{
if (tl == tr)
{
t[pos]--;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(t, tl, m, x, pos * 2);
else
ubd(t, m + 1, tr, x, pos * 2 + 1);
t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("c.in", "r", stdin);
scanf("%d%d%d%d%d", &n, &m ,&r, &q, &k);
sar(a, n, m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
sar(tt, n, m * 4);
for (int i = 1; i <= n; ++i)
bil(a[i], tt[i], 1, m, 1);
sar(ts, m, n * 4);
for (int j = 1; j <= m; ++j)
{
int* b;
b = new int[n + 5];
for (int i = 0; i < n + 5; ++i)
b[i] = 0;
for (int i = 1; i <= n; ++i)
b[i] = a[i][j];
bil(b, ts[j], 1, n, 1);
}
while (q--)
{
char u;
scanf(" %c", &u);
if (u == 'W')
{
int i, h;
scanf("%d%d", &i, &h);
v.clear();
qryl(tt[i], 1, m, h, 1);
while (v.size() > r)
v.pop_back();
for (int vi = 0; vi < v.size(); ++vi)
{
int j = v[vi];
ubd(tt[i], 1, m, j, 1);
ubd(ts[j], 1, n, i, 1);
}
}
else if (u == 'E')
{
int i, h;
scanf("%d%d", &i, &h);
v.clear();
qryr(tt[i], 1, m, h, 1);
while (v.size() > r)
v.pop_back();
for (int vi = 0; vi < v.size(); ++vi)
{
int j = v[vi];
ubd(tt[i], 1, m, j, 1);
ubd(ts[j], 1, n, i, 1);
}
}
else if (u == 'N')
{
int j, h;
scanf("%d%d", &j, &h);
v.clear();
qryl(ts[j], 1, n, h, 1);
while (v.size() > r)
v.pop_back();
for (int vi = 0; vi < v.size(); ++vi)
{
int i = v[vi];
ubd(tt[i], 1, m, j, 1);
ubd(ts[j], 1, n, i, 1);
}
}
else
{
int j, h;
scanf("%d%d", &j, &h);
v.clear();
qryr(ts[j], 1, n, h, 1);
while (v.size() > r)
v.pop_back();
for (int vi = 0; vi < v.size(); ++vi)
{
int i = v[vi];
ubd(tt[i], 1, m, j, 1);
ubd(ts[j], 1, n, i, 1);
}
}
}
long long **p;
p = new long long*[n + 5];
for (int i = 0; i < n + 5; ++i)
p[i] = new long long[m + 5];
for (int i = 0; i < n + 5; ++i)
for (int j = 0; j < m + 5; ++j)
p[i][j] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + qry(tt[i], 1, m, j, 1);
//cout << qry(tt[i], 1, m, j, 1) << ' ';
}
//cout << endl;
}
long long ans = 0;
for (int i = k; i <= n; ++i)
{
for (int j = k; j <= m; ++j)
{
ans = max(ans, p[i][j] - p[i][j - k] - p[i - k][j] + p[i - k][j - k]);
}
}
cout << ans << endl;
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||