| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 96012 | 2019-02-05T08:05:11 Z | Kastanda | UFO (IZhO14_ufo) | C++11 | 967 ms | 263168 KB |
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md (l + r >> 1)
using namespace std;
typedef vector < int > vi;
struct SegTree
{
int N;
vi MX, res;
int k, val, _back, i;
inline SegTree(int _N = 0)
{
N = _N;
MX.resize((N + 3) << 2);
}
inline void Setter(int _i, int _val) {i = _i; val = _val; Set(1, 0, N);}
inline void Getter(int _k, int _val, int __back) {k = _k; val = _val; _back = __back; res.clear(); Get(1, 0, N);}
void Set(int id, int l, int r)
{
if (r - l < 2)
{
MX[id] = val;
return ;
}
if (i < md)
Set(lc, l, md);
else
Set(rc, md, r);
MX[id] = max(MX[lc], MX[rc]);
}
void Get(int id, int l, int r)
{
if ((int)res.size() == k || MX[id] < val)
return ;
if (r - l < 2)
{res.push_back(l); return ;}
if (!_back)
Get(lc, l, md), Get(rc, md, r);
else
Get(rc, md, r), Get(lc, l, md);
return ;
}
};
int N, M, R;
int n, m, q, p_p;
vector < vi > A;
vector < SegTree > rows, cols;
int main()
{
scanf("%d%d%d%d%d", &n, &m, &R, &q, &p_p);
N = n + 5; M = m + 5;
A = vector < vi > (N, vi(M, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &A[i][j]);
rows.resize(N, SegTree(M));
cols.resize(M, SegTree(N));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
rows[i].Setter(j, A[i][j]);
cols[j].Setter(i, A[i][j]);
}
for (int i = 1; i <= q; i++)
{
int id, h;
char ch;
getchar(); ch = getchar();
scanf("%d%d", &id, &h);
id --;
if (ch == 'N' || ch == 'S')
{
cols[id].Getter(R, h, (ch == 'S'));
for (int &l : cols[id].res)
{
A[l][id] --;
cols[id].Setter(l, A[l][id]);
rows[l].Setter(id, A[l][id]);
}
}
else
{
rows[id].Getter(R, h, (ch == 'E'));
for (int &l : rows[id].res)
{
A[id][l] --;
rows[id].Setter(l, A[id][l]);
cols[l].Setter(id, A[id][l]);
}
}
}
long long sum = 0, Mx = 0;
for (int i = 0; i + p_p <= n; i++)
{
sum = 0;
for (int j = 0; j < m; j++)
{
for (int h = 0; h < p_p; h++)
sum += A[i + h][j];
if (j >= p_p)
for (int h = 0; h < p_p; h++)
sum -= A[i + h][j - p_p];
Mx = max(Mx, sum);
}
}
return !printf("%lld\n", Mx);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 5 ms | 760 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Correct | 2 ms | 256 KB | Output is correct |
| 3 | Runtime error | 3 ms | 764 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Correct | 15 ms | 988 KB | Output is correct |
| 5 | Correct | 77 ms | 4504 KB | Output is correct |
| 6 | Correct | 241 ms | 21512 KB | Output is correct |
| 7 | Runtime error | 388 ms | 138740 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Runtime error | 368 ms | 135120 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 | Runtime error | 376 ms | 104268 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 | Runtime error | 324 ms | 135032 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 | Correct | 433 ms | 74956 KB | Output is correct |
| 12 | Runtime error | 327 ms | 135064 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 | Runtime error | 278 ms | 143836 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 | Correct | 581 ms | 75212 KB | Output is correct |
| 15 | Correct | 685 ms | 71764 KB | Output is correct |
| 16 | Runtime error | 315 ms | 144716 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 | Correct | 967 ms | 80440 KB | Output is correct |
| 18 | Runtime error | 273 ms | 145444 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 | Runtime error | 363 ms | 196904 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 | Runtime error | 363 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |