| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 655593 |
2022-11-04T19:39:09 Z |
KiriLL1ca |
UFO (IZhO14_ufo) |
C++17 |
|
854 ms |
98724 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef unsigned int uint;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
struct segtree {
int n; vector <int> t;
segtree (int n = 0) : n(n), t(4 * n) {}
inline void upd (int v, int tl, int tr, int pos, int x) {
if (tl == tr) return void(t[v] = x);
int tm = (tl + tr) >> 1;
if (pos <= tm) upd(v << 1, tl, tm, pos, x);
else upd(v << 1 | 1, tm + 1, tr, pos, x);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
inline int lef (int v, int tl, int tr, int i, int x) {
if (t[v] < x || tr < i) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) >> 1;
int a = lef(v << 1, tl, tm, i, x);
if (!~a) return lef(v << 1 | 1, tm + 1, tr, i, x);
return a;
}
inline int rig (int v, int tl, int tr, int i, int x) {
if (t[v] < x || tl > i) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) >> 1;
int a = rig(v << 1 | 1, tm + 1, tr, i, x);
if (!~a) return rig(v << 1, tl, tm, i, x);
return a;
}
inline void upd (int pos, int x) { upd(1, 0, n - 1, pos, x); }
inline int lef (int i, int x) { return lef(1, 0, n - 1, i, x); }
inline int rig (int i, int x) { return rig(1, 0, n - 1, i, x); }
};
inline void solve () {
int n, m, r, q, p; cin >> n >> m >> r >> q >> p;
vector <segtree> row (n, segtree (m)), col (m, segtree (n));
vector <vector <ll>> a (n, vector <ll> (m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
row[i].upd(j, a[i][j]);
col[j].upd(i, a[i][j]);
}
}
while (q--) {
char c; int id, x; cin >> c >> id >> x; --id;
if (c == 'N') {
int cur = 0;
for (int it = 0; it < r; ++it) {
int pos = col[id].lef(cur, x);
if (!~pos) break;
--a[pos][id];
col[id].upd(pos, a[pos][id]);
row[pos].upd(id, a[pos][id]);
cur = pos + 1;
}
}
else if (c == 'S') {
int cur = n - 1;
for (int it = 0; it < r; ++it) {
int pos = col[id].rig(cur, x);
if (!~pos) break;
--a[pos][id];
col[id].upd(pos, a[pos][id]);
row[pos].upd(id, a[pos][id]);
cur = pos - 1;
}
}
else if (c == 'W') {
int cur = 0;
for (int it = 0; it < r; ++it) {
int pos = row[id].lef(cur, x);
if (!~pos) break;
--a[id][pos];
row[id].upd(pos, a[id][pos]);
col[pos].upd(id, a[id][pos]);
cur = pos + 1;
}
}
else if (c == 'E') {
int cur = m - 1;
for (int it = 0; it < r; ++it) {
int pos = row[id].rig(cur, x);
if (!~pos) break;
--a[id][pos];
row[id].upd(pos, a[id][pos]);
col[pos].upd(id, a[id][pos]);
cur = pos - 1;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i) a[i][j] += a[i - 1][j];
if (j) a[i][j] += a[i][j - 1];
if (i && j) a[i][j] -= a[i - 1][j - 1];
}
}
auto get = [&] (int i, int j, int ii, int jj) { return a[ii][jj] - (i ? a[i - 1][jj] : 0) - (j ? a[ii][j - 1] : 0) + (i && j ? a[i - 1][j - 1] : 0); };
ll ans = 0;
for (int i = 0; i + p - 1 < n; ++i) {
for (int j = 0; j + p - 1 < m; ++j) {
umax(ans, get(i, j, i + p - 1, j + p - 1));
}
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1; // cin >> t;
while (t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
13 ms |
852 KB |
Output is correct |
| 5 |
Correct |
71 ms |
3188 KB |
Output is correct |
| 6 |
Correct |
179 ms |
22892 KB |
Output is correct |
| 7 |
Correct |
265 ms |
52764 KB |
Output is correct |
| 8 |
Correct |
197 ms |
49292 KB |
Output is correct |
| 9 |
Correct |
457 ms |
45704 KB |
Output is correct |
| 10 |
Correct |
497 ms |
48520 KB |
Output is correct |
| 11 |
Correct |
353 ms |
47656 KB |
Output is correct |
| 12 |
Correct |
520 ms |
48396 KB |
Output is correct |
| 13 |
Correct |
610 ms |
52552 KB |
Output is correct |
| 14 |
Correct |
443 ms |
47732 KB |
Output is correct |
| 15 |
Correct |
596 ms |
49932 KB |
Output is correct |
| 16 |
Correct |
214 ms |
49840 KB |
Output is correct |
| 17 |
Correct |
845 ms |
56920 KB |
Output is correct |
| 18 |
Correct |
233 ms |
47976 KB |
Output is correct |
| 19 |
Correct |
326 ms |
55432 KB |
Output is correct |
| 20 |
Correct |
854 ms |
98724 KB |
Output is correct |
