| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 144293 |
2019-08-16T14:35:36 Z |
SamAnd |
UFO (IZhO14_ufo) |
C++17 |
|
1437 ms |
255608 KB |
#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
ufo.cpp: In function 'void qryl(int*&, int, int, int, int)':
ufo.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (v.size() > r)
~~~~~~~~~^~~
ufo.cpp: In function 'void qryr(int*&, int, int, int, int)':
ufo.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (v.size() > r)
~~~~~~~~~^~~
ufo.cpp: In function 'int main()':
ufo.cpp:120:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (v.size() > r)
~~~~~~~~~^~~
ufo.cpp:122:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int vi = 0; vi < v.size(); ++vi)
~~~^~~~~~~~~~
ufo.cpp:135:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (v.size() > r)
~~~~~~~~~^~~
ufo.cpp:137:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int vi = 0; vi < v.size(); ++vi)
~~~^~~~~~~~~~
ufo.cpp:150:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (v.size() > r)
~~~~~~~~~^~~
ufo.cpp:152:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int vi = 0; vi < v.size(); ++vi)
~~~^~~~~~~~~~
ufo.cpp:165:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (v.size() > r)
~~~~~~~~~^~~
ufo.cpp:167:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int vi = 0; vi < v.size(); ++vi)
~~~^~~~~~~~~~
ufo.cpp:91: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, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:95: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:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &u);
~~~~~^~~~~~~~~~~
ufo.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &i, &h);
~~~~~^~~~~~~~~~~~~~~~
ufo.cpp:132:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &i, &h);
~~~~~^~~~~~~~~~~~~~~~
ufo.cpp:147:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &j, &h);
~~~~~^~~~~~~~~~~~~~~~
ufo.cpp:162:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &j, &h);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
23 ms |
1016 KB |
Output is correct |
| 5 |
Correct |
116 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
254 ms |
26812 KB |
Output is correct |
| 7 |
Correct |
399 ms |
74372 KB |
Output is correct |
| 8 |
Correct |
322 ms |
73336 KB |
Output is correct |
| 9 |
Correct |
579 ms |
61304 KB |
Output is correct |
| 10 |
Correct |
750 ms |
72460 KB |
Output is correct |
| 11 |
Correct |
545 ms |
73556 KB |
Output is correct |
| 12 |
Correct |
775 ms |
72568 KB |
Output is correct |
| 13 |
Correct |
861 ms |
73720 KB |
Output is correct |
| 14 |
Correct |
753 ms |
73592 KB |
Output is correct |
| 15 |
Correct |
916 ms |
74036 KB |
Output is correct |
| 16 |
Correct |
351 ms |
75768 KB |
Output is correct |
| 17 |
Correct |
1233 ms |
74596 KB |
Output is correct |
| 18 |
Correct |
283 ms |
72040 KB |
Output is correct |
| 19 |
Correct |
513 ms |
93304 KB |
Output is correct |
| 20 |
Correct |
1437 ms |
255608 KB |
Output is correct |
