| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 344731 |
2021-01-06T11:20:26 Z |
_ani |
UFO (IZhO14_ufo) |
C++17 |
|
441 ms |
177136 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int inf = 1'000'000'000;
vector<vector<ll>> a;
vector<vector<ll>> tr, tc;
void Buildr(int v, int vl, int vr, int i) {//checked
if (vl == vr) {
tr[i][v] = a[i][vl];
return;
}
int m = (vl + vr) / 2;
Buildr(v * 2, vl, m, i);
Buildr(v * 2 + 1, m + 1, vr, i);
tr[i][v] = max(tr[i][v * 2], tr[i][v * 2 + 1]);
}
void Buildc(int v, int vl, int vr, int j) {//checked
if (vl == vr) {
tc[j][v] = a[vl][j];
return;
}
int m = (vl + vr) / 2;
Buildc(v * 2, vl, m, j);
Buildc(v * 2 + 1, m + 1, vr, j);
tc[j][v] = max(tc[j][v * 2], tc[j][v * 2 + 1]);
}
int RFirstGreater(int v, int vl, int vr, int l, int r, int i, ll k) {//checked
if (vl == vr) {
if (tr[i][v] >= k)return vl;
return inf;
}
if (vl == l && vr == r) {
if (tr[i][v] < k)return inf;
if (tr[i][v * 2] >= k)
return RFirstGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, i, k);
return RFirstGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, i, k);
}
int m = (vl + vr) / 2;
if (r <= m)return RFirstGreater(v * 2, vl, m, l, r, i, k);
if (l > m)return RFirstGreater(v * 2 + 1, m + 1, vr, l, r, i, k);
int res = inf;
res = min(res, RFirstGreater(v * 2, vl, m, l, min(r, m), i, k));
res = min(res, RFirstGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, i, k));
return res;
}
int RLastGreater(int v, int vl, int vr, int l, int r, int i, ll k) {//checked
if (vl == vr) {
if (tr[i][v] >= k)return vl;
return -1;
}
if (vl == l && vr == r) {
if (tr[i][v] < k)return -1;
if (tr[i][v * 2] >= k)
return RLastGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, i, k);
return RLastGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, i, k);
}
int m = (vl + vr) / 2;
if (r <= m)return RLastGreater(v * 2, vl, m, l, r, i, k);
if (l > m)return RLastGreater(v * 2 + 1, m + 1, vr, l, r, i, k);
int res = inf;
res = max(res, RLastGreater(v * 2, vl, m, l, min(r, m), i, k));
res = max(res, RLastGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, i, k));
return res;
}
int CFirstGreater(int v, int vl, int vr, int l, int r, int j, ll k) {//checked
if (vl == vr) {
if (tc[j][v] >= k)return vl;
return inf;
}
if (vl == l && vr == r) {
if (tc[j][v] < k)return inf;
if (tc[j][v * 2] >= k)
return CFirstGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, j, k);
return CFirstGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, j, k);
}
int m = (vl + vr) / 2;
if (r <= m)return CFirstGreater(v * 2, vl, m, l, r, j, k);
if (l > m)return CFirstGreater(v * 2 + 1, m + 1, vr, l, r, j, k);
int res = inf;
res = min(res, CFirstGreater(v * 2, vl, m, l, min(r, m), j, k));
res = min(res, CFirstGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, j, k));
return res;
}
int CLastGreater(int v, int vl, int vr, int l, int r, int j, ll k) {//checked
if (vl == vr) {
if (tc[j][v] >= k)return vl;
return -1;
}
if (vl == l && vr == r) {
if (tc[j][v] < k)return -1;
if (tc[j][v * 2] >= k)
return CLastGreater(v * 2, vl, (vl + vr) / 2, vl, (vl + vr) / 2, j, k);
return CLastGreater(v * 2 + 1, (vl + vr) / 2 + 1, vr, (vl + vr) / 2 + 1, vr, j, k);
}
int m = (vl + vr) / 2;
if (r <= m)return CLastGreater(v * 2, vl, m, l, r, j, k);
if (l > m)return CLastGreater(v * 2 + 1, m + 1, vr, l, r, j, k);
int res = inf;
res = max(res, CLastGreater(v * 2, vl, m, l, min(r, m), j, k));
res = max(res, CLastGreater(v * 2 + 1, m + 1, vr, max(l, m + 1), r, j, k));
return res;
}
void RUpd(int v, int vl, int vr, int i, int j) {//checked
if (vl == vr) {
tr[i][v]--;
return;
}
int m = (vl + vr) / 2;
if (j <= m)
RUpd(v * 2, vl, m, i, j);
else
RUpd(v * 2 + 1, m + 1, vr, i, j);
tr[i][v] = max(tr[i][v * 2], tr[i][v * 2 + 1]);
}
void CUpd(int v, int vl, int vr, int i, int j) {//checked
if (vl == vr) {
tc[j][v]--;
return;
}
int m = (vl + vr) / 2;
if (i <= m)
CUpd(v * 2, vl, m, i, j);
else
CUpd(v * 2 + 1, m + 1, vr, i, j);
tc[j][v] = max(tc[j][v * 2], tc[j][v * 2 + 1]);
}
ll Get(int v, int vl, int vr, int i, int j) {//checked
if (vl == vr)return tr[i][v];
int m = (vl + vr) / 2;
if (j <= m)return Get(v * 2, vl, m, i, j);
return Get(v * 2 + 1, m + 1, vr, i, j);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, r, k, p;
cin >> n >> m >> r >> k >> p;
a.resize(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
ll x;
cin >> x;
a[i].push_back(x);
}
tr.resize(n);
for (int i = 0; i < n; i++) {
tr[i].resize(4 * m + 4);
Buildr(1, 0, m - 1, i);
}
tc.resize(m);
for (int j = 0; j < m; j++) {
tc[j].resize(4 * n + 4);
Buildc(1, 0, n - 1, j);
}
while (k--)
{
char s;
int x;
ll h;
cin >> s >> x >> h;
x--;
int ind;
if (s == 'W' || s == 'N')ind = -1;
else ind = inf;
for (int i = 0; i < r; i++) {
if (s == 'W') {
int cur = RFirstGreater(1, 0, m - 1, ind + 1, m - 1, x, h);
// cerr << "cur index " << cur << '\n';
if (cur == inf) break;
RUpd(1, 0, m - 1, x, cur);
CUpd(1, 0, n - 1, x, cur);
ind = cur;
if (ind + 1 >= m)
break;
}
if (s == 'N') {
int cur = CFirstGreater(1, 0, n - 1, ind + 1, n - 1, x, h);
// cerr << "cur index " << cur << '\n';
if (cur == inf) break;
RUpd(1, 0, m - 1, cur, x);
CUpd(1, 0, n - 1, cur, x);
ind = cur;
if (ind + 1 >= n)
break;
}
if (s == 'E') {
int cur = RLastGreater(1, 0, m - 1, 0, min(ind, m) - 1, x, h);
// cerr << "cur index " << cur << '\n';
if (cur == -1) break;
RUpd(1, 0, m - 1, x, cur);
CUpd(1, 0, n - 1, x, cur);
ind = cur;
if (ind - 1 < 0)
break;
}
if (s == 'S') {
int cur = CLastGreater(1, 0, n - 1, 0, min(ind, n) - 1, x, h);
// cerr << "cur index " << cur << '\n';
if (cur == -1) break;
RUpd(1, 0, m - 1, cur, x);
CUpd(1, 0, n - 1, cur, x);
ind = cur;
if (ind - 1 < 0)
break;
}
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
a[i][j] = Get(1, 0, m - 1, i, j);
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// cerr << a[i][j] << ' ';
if (i + p > n || j + p > m)continue;
ll cur = 0;
for (int x = i; x < i + p; x++)
for (int y = j; y < j + p; y++)
cur += a[x][y];
ans = max(ans, cur);
}
// cerr << '\n';
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Runtime error |
2 ms |
876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
4 ms |
2028 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Incorrect |
131 ms |
4588 KB |
Output isn't correct |
| 6 |
Runtime error |
141 ms |
74460 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
277 ms |
158220 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
261 ms |
158448 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
243 ms |
152124 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
252 ms |
159220 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
247 ms |
156420 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
255 ms |
159484 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
298 ms |
176876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
346 ms |
157160 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
259 ms |
159628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
245 ms |
156788 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
329 ms |
177136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
251 ms |
151020 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
276 ms |
174240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Correct |
441 ms |
145908 KB |
Output is correct |
