| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 226287 |
2020-04-23T09:57:58 Z |
emil_physmath |
UFO (IZhO14_ufo) |
C++17 |
|
2000 ms |
98604 KB |
#include <iostream>
#include <vector>
using namespace std;
int shots;
int n, m;
vector<vector<int> > a;
vector<int> tcol[1000'000], trow[1000'000];
void Shoot(const vector<int>& t, int v, int vl, int vr, int hei, int dir, vector<int>& ans)
{
if (ans.size() == shots) return;
if (t[v] < hei) return;
if (vl == vr)
{
ans.push_back(vr);
return;
}
int vm = (vl + vr) / 2;
if (dir == 1)
{
Shoot(t, v * 2, vl, vm, hei, dir, ans);
Shoot(t, v * 2 + 1, vm + 1, vr, hei, dir, ans);
}
else
{
Shoot(t, v * 2 + 1, vm + 1, vr, hei, dir, ans);
Shoot(t, v * 2, vl, vm, hei, dir, ans);
}
}
void Add(vector<int>& t, int v, int vl, int vr, int i, int val)
{
if (vl == vr)
{
t[v] += val;
return;
}
int vm = (vl + vr) / 2;
if (i <= vm) Add(t, v * 2, vl, vm, i, val);
else Add(t, v * 2 + 1, vm + 1, vr, i, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void SetRow(int i, int v, int vl, int vr)
{
if (vl == vr)
{
a[i][vr] = trow[i][v];
return;
}
int vm = (vl + vr) / 2;
SetRow(i, v * 2, vl, vm);
SetRow(i, v * 2 + 1, vm + 1, vr);
}
int main()
{
int qnum, anpetq;
cin >> n >> m >> shots >> qnum >> anpetq;
a.resize(n, vector<int>(m));
for (int i = 0; i < n; ++i)
trow[i].resize(4 * m);
for (int j = 0; j < m; ++j)
tcol[j].resize(4 * n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
cin >> a[i][j];
Add(trow[i], 1, 0, m - 1, j, a[i][j]);
Add(tcol[j], 1, 0, n - 1, i, a[i][j]);
}
while (qnum--)
{
char dir;
int i, hei;
cin >> dir >> i >> hei;
int j = --i;
vector<int> col;
vector<int> row;
if (dir == 'W')
Shoot(trow[i], 1, 0, m - 1, hei, 1, col);
else if (dir == 'E')
Shoot(trow[i], 1, 0, m - 1, hei, -1, col);
else if (dir == 'N')
Shoot(tcol[j], 1, 0, n - 1, hei, 1, row);
else // 'S'
Shoot(tcol[j], 1, 0, n - 1, hei, -1, row);
if (dir == 'W' || dir == 'E')
for (int j: col)
{
Add(trow[i], 1, 0, m - 1, j, -1);
Add(tcol[j], 1, 0, n - 1, i, -1);
}
else
for (int i: row)
{
Add(trow[i], 1, 0, m - 1, j, -1);
Add(tcol[j], 1, 0, n - 1, i, -1);
}
}
for (int i = 0; i < n; ++i)
SetRow(i, 1, 0, m - 1);
int ans = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
#ifdef MANSON
cerr << a[i][j] << ' ';
#endif
if (i + anpetq - 1 >= n || j + anpetq - 1 >= m) continue;
int cur = 0;
for (int di = 0; di < anpetq; ++di)
for (int dj = 0; dj < anpetq; ++dj)
cur += a[i + di][j + dj];
ans = max(ans, cur);
}
#ifdef MANSON
cerr << '\n';
#endif
}
cout << ans;
}
Compilation message
ufo.cpp: In function 'void Shoot(const std::vector<int>&, int, int, int, int, int, std::vector<int>&)':
ufo.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ans.size() == shots) return;
~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
47224 KB |
Output is correct |
| 2 |
Correct |
32 ms |
47360 KB |
Output is correct |
| 3 |
Correct |
31 ms |
47352 KB |
Output is correct |
| 4 |
Correct |
59 ms |
47744 KB |
Output is correct |
| 5 |
Correct |
194 ms |
49528 KB |
Output is correct |
| 6 |
Correct |
506 ms |
65144 KB |
Output is correct |
| 7 |
Correct |
902 ms |
84568 KB |
Output is correct |
| 8 |
Correct |
666 ms |
84592 KB |
Output is correct |
| 9 |
Correct |
957 ms |
83836 KB |
Output is correct |
| 10 |
Correct |
1097 ms |
84572 KB |
Output is correct |
| 11 |
Correct |
816 ms |
83488 KB |
Output is correct |
| 12 |
Correct |
1090 ms |
84536 KB |
Output is correct |
| 13 |
Correct |
1341 ms |
87672 KB |
Output is correct |
| 14 |
Correct |
1193 ms |
83488 KB |
Output is correct |
| 15 |
Correct |
1407 ms |
84592 KB |
Output is correct |
| 16 |
Correct |
736 ms |
83488 KB |
Output is correct |
| 17 |
Execution timed out |
2037 ms |
87672 KB |
Time limit exceeded |
| 18 |
Correct |
702 ms |
84472 KB |
Output is correct |
| 19 |
Correct |
904 ms |
86120 KB |
Output is correct |
| 20 |
Correct |
1960 ms |
98604 KB |
Output is correct |
