| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 917472 |
2024-01-28T09:06:57 Z |
atom |
UFO (IZhO14_ufo) |
C++17 |
|
1849 ms |
239220 KB |
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
template <typename T>
struct SegmentTree {
vector <T> f, a;
int n;
T NEUTRAL = numeric_limits <T> :: min();
SegmentTree (int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
f.assign((n << 1) + 5, NEUTRAL);
a.resize(n + 5);
}
T merge(T x, T y) { return max(x, y); }
void build() {
for (int x = 1; x <= n; ++x) f[x + n] = a[x];
for (int x = n; x >= 1; --x)
f[x] = merge(f[x << 1], f[x << 1 | 1]);
}
void upd(int p, int val) {
f[p += n] += val;
for (; p > 0; p >>= 1)
f[p >> 1] = merge(f[p], f[p ^ 1]);
}
T qry(int p) { return f[p + n]; }
T qry(int l, int r) {
T ql = NEUTRAL;
T qr = NEUTRAL;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) ql = merge(ql, f[l++]);
if (r & 1) qr = merge(f[--r], qr);
}
return merge(ql, qr);
}
// t = 0, find first element >= x to the left, t = 1 ..to the right
T get(int p, int x, int t) {
int l = (t? p : 1);
int r = (t? n : p);
int ans = -1;
while (l <= r) {
int m = (l + r) >> 1;
if ((t? qry(l, m) : qry(m, r)) >= x) {
ans = m;
t? (r = m - 1) : l = (m + 1);
}
else t? (l = m + 1) : (r = m - 1);
}
return ans;
}
};
int n, m, rd, k, p;
vector <vector <int>> sh;
vector <SegmentTree <int>> col, row;
signed main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m >> rd >> k >> p;
sh.assign(n + 5, vector <int> (m + 5, 0));
row.resize(n + 5);
col.resize(m + 5);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> sh[i][j];
for (int i = 1; i <= n; ++i) {
row[i].init(m);
for (int j = 1; j <= m; ++j) row[i].a[j] = sh[i][j];
row[i].build();
}
for (int i = 1; i <= m; ++i) {
col[i].init(n);
for (int j = 1; j <= n; ++j) col[i].a[j] = sh[j][i];
col[i].build();
}
// rd <= 10? -> Q*10*log(N);
for (int _i = 1; _i <= k; ++_i) {
char cmd; int x, h;
cin >> cmd >> x >> h;
int cnt = rd;
if (cmd == 'N' || cmd == 'S') {
int t = (cmd == 'N');
int pos = (cmd == 'N'? 1 : n);
int y = col[x].get(pos, h, t);
while (y != -1 && cnt > 0) {
col[x].upd(y, -1);
row[y].upd(x, -1);
y = col[x].get(y + (cmd == 'N'? 1 : -1), h, t);
--cnt;
}
}
else {
int t = (cmd == 'W');
int pos = (cmd == 'W'? 1 : m);
int y = row[x].get(pos, h, t);
while (y != -1 && cnt > 0) {
row[x].upd(y, -1);
col[y].upd(x, -1);
y = row[x].get(y + (cmd == 'W'? 1 : -1), h, t);
--cnt;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
sh[i][j] = col[j].qry(i);
// cout << sh[i][j] << " \n"[j == m];
}
}
vector <vector <ll>> prf(n + 5, vector <ll> (m + 5, 0));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
prf[i][j] = prf[i - 1][j] + prf[i][j - 1] - prf[i - 1][j - 1] + sh[i][j];
auto qry = [&] (int x, int y, int X, int Y) {
return prf[X][Y] + prf[x - 1][y - 1] - prf[X][y - 1] - prf[x - 1][Y];
};
ll ans = 0;
for (int r = 1; r + p - 1 <= n; ++r) {
for (int c = 1; c + p - 1 <= m; ++c) {
int R = r + p - 1; int C = c + p - 1;
ll sum = qry(r, c, R, C);
if (ans < sum) {
// debug(r, c, R, C);
ans = sum;
}
}
}
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
10 ms |
604 KB |
Output is correct |
| 5 |
Correct |
73 ms |
3096 KB |
Output is correct |
| 6 |
Correct |
130 ms |
17744 KB |
Output is correct |
| 7 |
Correct |
235 ms |
54988 KB |
Output is correct |
| 8 |
Correct |
199 ms |
54988 KB |
Output is correct |
| 9 |
Correct |
702 ms |
44748 KB |
Output is correct |
| 10 |
Correct |
1079 ms |
54960 KB |
Output is correct |
| 11 |
Correct |
738 ms |
56324 KB |
Output is correct |
| 12 |
Correct |
1199 ms |
54956 KB |
Output is correct |
| 13 |
Correct |
1271 ms |
61348 KB |
Output is correct |
| 14 |
Correct |
753 ms |
56328 KB |
Output is correct |
| 15 |
Correct |
1210 ms |
54952 KB |
Output is correct |
| 16 |
Correct |
244 ms |
56440 KB |
Output is correct |
| 17 |
Correct |
1849 ms |
61304 KB |
Output is correct |
| 18 |
Correct |
248 ms |
61944 KB |
Output is correct |
| 19 |
Correct |
577 ms |
73284 KB |
Output is correct |
| 20 |
Correct |
1020 ms |
239220 KB |
Output is correct |
