| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 226289 |
2020-04-23T09:59:59 Z |
emil_physmath |
UFO (IZhO14_ufo) |
C++17 |
|
1628 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()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
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 |
28 ms |
47360 KB |
Output is correct |
| 2 |
Correct |
31 ms |
47352 KB |
Output is correct |
| 3 |
Correct |
30 ms |
47480 KB |
Output is correct |
| 4 |
Correct |
50 ms |
47744 KB |
Output is correct |
| 5 |
Correct |
163 ms |
49528 KB |
Output is correct |
| 6 |
Correct |
377 ms |
64928 KB |
Output is correct |
| 7 |
Correct |
480 ms |
84516 KB |
Output is correct |
| 8 |
Correct |
401 ms |
84464 KB |
Output is correct |
| 9 |
Correct |
719 ms |
83736 KB |
Output is correct |
| 10 |
Correct |
931 ms |
84488 KB |
Output is correct |
| 11 |
Correct |
677 ms |
83412 KB |
Output is correct |
| 12 |
Correct |
941 ms |
84516 KB |
Output is correct |
| 13 |
Correct |
1108 ms |
87620 KB |
Output is correct |
| 14 |
Correct |
993 ms |
83360 KB |
Output is correct |
| 15 |
Correct |
1143 ms |
84508 KB |
Output is correct |
| 16 |
Correct |
418 ms |
83356 KB |
Output is correct |
| 17 |
Correct |
1574 ms |
87628 KB |
Output is correct |
| 18 |
Correct |
404 ms |
84328 KB |
Output is correct |
| 19 |
Correct |
558 ms |
85992 KB |
Output is correct |
| 20 |
Correct |
1628 ms |
98604 KB |
Output is correct |
