| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 133870 |
2019-07-21T15:49:03 Z |
Kastanda |
UFO (IZhO14_ufo) |
C++11 |
|
1016 ms |
183288 KB |
// ItnoE
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md (l + r >> 1)
using namespace std;
int R, ts, val, ii, ret[11];
struct Tree
{
int N, * MX;
inline Tree(int _N = 0)
{
N = _N;
MX = new int [N + 3 << 2];
}
inline void Setter(int _ii, int _val)
{
ii = _ii;
val = _val;
Set(1, 1, N + 1);
}
inline void Getter(int _val, int d)
{
ts = 0;
val = _val;
if (d == 0)
GetPref(1, 1, N + 1);
else
GetSuff(1, 1, N + 1);
}
void Set(int id, int l, int r)
{
if (r - l < 2)
return void(MX[id] = val);
if (ii < md)
Set(lc, l, md);
else
Set(rc, md, r);
MX[id] = max(MX[lc], MX[rc]);
}
void GetPref(int id, int l, int r)
{
if (MX[id] < val || ts >= R)
return ;
if (r - l < 2)
return void(ret[ts ++] = l);
GetPref(lc, l, md);
GetPref(rc, md, r);
}
void GetSuff(int id, int l, int r)
{
if (MX[id] < val || ts >= R)
return ;
if (r - l < 2)
return void(ret[ts ++] = l);
GetSuff(rc, md, r);
GetSuff(lc, l, md);
}
};
int main()
{
int n, m, q, p;
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> R >> q >> p;
int A[n + 3][m + 3];
memset(A, 0, sizeof(A));
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
cin >> A[i][j];
Tree rows[n + 3], cols[m + 3];
for (int i = 1; i <= n; i ++)
rows[i] = Tree(m);
for (int i = 1; i <= m; i ++)
cols[i] = Tree(n);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
rows[i].Setter(j, A[i][j]);
cols[j].Setter(i, A[i][j]);
}
for (; q; q --)
{
char ch;
int id, h;
cin >> ch >> id >> h;
if (ch == 'W' || ch == 'E')
{
rows[id].Getter(h, ch == 'E');
for (int i = 0; i < ts; i ++)
{
A[id][ret[i]] --;
rows[id].Setter(ret[i], A[id][ret[i]]);
cols[ret[i]].Setter(id, A[id][ret[i]]);
}
}
else
{
cols[id].Getter(h, ch == 'S');
for (int i = 0; i < ts; i ++)
{
A[ret[i]][id] --;
rows[ret[i]].Setter(id, A[ret[i]][id]);
cols[id].Setter(ret[i], A[ret[i]][id]);
}
}
}
int Mx = 0;
for (int i = p; i <= n; i ++)
for (int j = p; j <= m; j ++)
{
int SM = 0;
for (int a = i - p + 1; a <= i; a ++)
for (int b = j - p + 1; b <= j; b ++)
SM += A[a][b];
Mx = max(Mx, SM);
}
return !printf("%d\n", Mx);
}
Compilation message
ufo.cpp: In constructor 'Tree::Tree(int)':
ufo.cpp:14:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
MX = new int [N + 3 << 2];
~~^~~
ufo.cpp: In member function 'void Tree::Set(int, int, int)':
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define md (l + r >> 1)
~~^~~
ufo.cpp:35:18: note: in expansion of macro 'md'
if (ii < md)
^~
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define md (l + r >> 1)
~~^~~
ufo.cpp:36:24: note: in expansion of macro 'md'
Set(lc, l, md);
^~
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define md (l + r >> 1)
~~^~~
ufo.cpp:38:21: note: in expansion of macro 'md'
Set(rc, md, r);
^~
ufo.cpp: In member function 'void Tree::GetPref(int, int, int)':
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define md (l + r >> 1)
~~^~~
ufo.cpp:47:24: note: in expansion of macro 'md'
GetPref(lc, l, md);
^~
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define md (l + r >> 1)
~~^~~
ufo.cpp:48:21: note: in expansion of macro 'md'
GetPref(rc, md, r);
^~
ufo.cpp: In member function 'void Tree::GetSuff(int, int, int)':
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define md (l + r >> 1)
~~^~~
ufo.cpp:56:21: note: in expansion of macro 'md'
GetSuff(rc, md, r);
^~
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define md (l + r >> 1)
~~^~~
ufo.cpp:57:24: note: in expansion of macro 'md'
GetSuff(lc, l, md);
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
21 ms |
760 KB |
Output is correct |
| 5 |
Correct |
91 ms |
2796 KB |
Output is correct |
| 6 |
Correct |
243 ms |
17784 KB |
Output is correct |
| 7 |
Correct |
369 ms |
47736 KB |
Output is correct |
| 8 |
Correct |
298 ms |
47756 KB |
Output is correct |
| 9 |
Correct |
503 ms |
39288 KB |
Output is correct |
| 10 |
Correct |
558 ms |
46948 KB |
Output is correct |
| 11 |
Correct |
429 ms |
46840 KB |
Output is correct |
| 12 |
Correct |
583 ms |
46880 KB |
Output is correct |
| 13 |
Correct |
651 ms |
47776 KB |
Output is correct |
| 14 |
Correct |
553 ms |
46884 KB |
Output is correct |
| 15 |
Correct |
667 ms |
47608 KB |
Output is correct |
| 16 |
Correct |
308 ms |
49016 KB |
Output is correct |
| 17 |
Correct |
959 ms |
48636 KB |
Output is correct |
| 18 |
Correct |
280 ms |
45916 KB |
Output is correct |
| 19 |
Correct |
416 ms |
63736 KB |
Output is correct |
| 20 |
Correct |
1016 ms |
183288 KB |
Output is correct |
