| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 96017 |
2019-02-05T08:27:58 Z |
Kastanda |
UFO (IZhO14_ufo) |
C++11 |
|
1032 ms |
173696 KB |
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef vector < int > vi;
int R, ts, res[15];
int val, ii, _back;
struct SegTree
{
int N, * MX;
inline SegTree(int _N = 0)
{
N = _N;
//MX.resize((N + 3) << 2);
MX = new int [(N + 3) * 4];
}
inline void Setter(int _i, int _val) {ii = _i; val = _val; Set(1, 0, N);}
inline void Getter(int _val, int __back) {val = _val; _back = __back; ts = 0; Get(1, 0, N);}
void Set(int id, int l, int r)
{
if (id >= ((N + 3) * 4) - 3)
assert(0);
if (r - l < 2)
{
MX[id] = val;
return ;
}
if (ii < 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 (id >= ((N + 3) * 4) - 3)
assert(0);
if (ts >= R || MX[id] < val)
return ;
if (r - l < 2)
{res[ts ++] = 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;
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));
int A[N][M]; // this is bad
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));
SegTree rows[N];
SegTree cols[M];
for (int i = 0; i < n; i++)
rows[i] = SegTree(m);
for (int i = 0; i < m; i++)
cols[i] = 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;
cin >> ch;
//getchar(); ch = getchar();
scanf("%d%d", &id, &h);
id --;
if (ch == 'N' || ch == 'S')
{
cols[id].Getter(h, (ch == 'S'));
for (int j = 0; j < ts; j++)
{
int &l = res[j];
A[l][id] --;
cols[id].Setter(l, A[l][id]);
rows[l].Setter(id, A[l][id]);
}
}
else
{
rows[id].Getter(h, (ch == 'E'));
for (int j = 0; j < ts; j++)
{
int &l = res[j];
A[id][l] --;
rows[id].Setter(l, A[id][l]);
cols[l].Setter(id, A[id][l]);
}
}
}
int 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("%d\n", Mx);
}
Compilation message
ufo.cpp: In function 'int main()':
ufo.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d", &n, &m, &R, &q, &p_p);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i][j]);
~~~~~^~~~~~~~~~~~~~~~
ufo.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &id, &h);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
16 ms |
760 KB |
Output is correct |
| 5 |
Correct |
79 ms |
2680 KB |
Output is correct |
| 6 |
Correct |
230 ms |
17784 KB |
Output is correct |
| 7 |
Correct |
369 ms |
46504 KB |
Output is correct |
| 8 |
Correct |
308 ms |
46640 KB |
Output is correct |
| 9 |
Correct |
472 ms |
38692 KB |
Output is correct |
| 10 |
Correct |
533 ms |
45688 KB |
Output is correct |
| 11 |
Correct |
421 ms |
44252 KB |
Output is correct |
| 12 |
Correct |
720 ms |
45816 KB |
Output is correct |
| 13 |
Correct |
623 ms |
47164 KB |
Output is correct |
| 14 |
Correct |
651 ms |
44324 KB |
Output is correct |
| 15 |
Correct |
682 ms |
44284 KB |
Output is correct |
| 16 |
Correct |
324 ms |
47752 KB |
Output is correct |
| 17 |
Correct |
1032 ms |
46316 KB |
Output is correct |
| 18 |
Correct |
264 ms |
44792 KB |
Output is correct |
| 19 |
Correct |
391 ms |
61320 KB |
Output is correct |
| 20 |
Correct |
896 ms |
173696 KB |
Output is correct |
