Submission #972980

#	Time	Username	Problem	Language	Result	Execution time	Memory
972980		MilosMilutinovic	UFO (IZhO14_ufo)	C++14	100 / 100	905 ms	173296 KiB

ufo

#include <bits/stdc++.h>
 
using namespace std;

struct segtree {
  vector<int> mx;
  segtree() {}
  segtree(int n) : mx(4 * n) {}
  void modify(int id, int l, int r, int i, int v) {
    if (l == r) {
      mx[id] += v;
      return;
    }
    int mid = (l + r) >> 1;
    if (i <= mid) {
      modify(id << 1, l, mid, i, v);
    } else {
      modify(id << 1 | 1, mid + 1, r, i, v);
    }
    mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
  }
  int find_first(int id, int l, int r, int i, int v) {
    if (r < i || mx[id] < v) {
      return -1;
    }
    if (l == r) {
      return l;
    }
    int mid = (l + r) / 2;
    int f = find_first(id << 1, l, mid, i, v);
    if (f != -1) {
      return f;
    } else {
      return find_first(id << 1 | 1, mid + 1, r, i, v);
    }
  }
};
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, r, k, p;
  cin >> n >> m >> r >> k >> p;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  vector<vector<segtree>> st(4);
  st[0] = vector<segtree>(n, segtree(m));
  st[1] = vector<segtree>(n, segtree(m));
  st[2] = vector<segtree>(m, segtree(n));
  st[3] = vector<segtree>(m, segtree(n));
  vector<vector<int>> b(n, vector<int>(m));
  auto Update = [&](int i, int j, int v) {
    st[0][i].modify(1, 0, m - 1, j, v);
    st[1][i].modify(1, 0, m - 1, m - 1 - j, v);
    st[2][j].modify(1, 0, n - 1, i, v);
    st[3][j].modify(1, 0, n - 1, n - 1 - i, v);
    b[i][j] += v;
  };
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      Update(i, j, a[i][j]);
    }
  }
  while (k--) {
    char op;
    cin >> op;
    if (op == 'W') {
      int i, h;
      cin >> i >> h;
      --i;
      int lst = 0;
      for (int it = 0; it < r && lst < m; it++) {
        int j = st[0][i].find_first(1, 0, m - 1, lst, h);
        if (j == -1) {
          break;
        }
        Update(i, j, -1);
        lst = j + 1;
      }
    }
    if (op == 'E') {
      int i, h;
      cin >> i >> h;
      --i;
      int lst = 0;
      for (int it = 0; it < r && lst < m; it++) {
        int j = st[1][i].find_first(1, 0, m - 1, lst, h);
        if (j == -1) {
          break;
        }
        Update(i, m - 1 - j, -1);
        lst = j + 1;
      }
    }
    if (op == 'N') {
      int j, h;
      cin >> j >> h;
      --j;
      int lst = 0;
      for (int it = 0; it < r && lst < n; it++) {
        int i = st[2][j].find_first(1, 0, n - 1, lst, h);
        if (i == -1) {
          break;
        }
        Update(i, j, -1);
        lst = i + 1;
      }
    }
    if (op == 'S') {
      int j, h;
      cin >> j >> h;
      --j;
      int lst = 0;
      for (int it = 0; it < r && lst < n; it++) {
        int i = st[3][j].find_first(1, 0, n - 1, lst, h);
        if (i == -1) {
          break;
        }
        Update(n - 1 - i, j, -1);
        lst = i + 1;
      }
    }
  }
  vector<vector<long long>> sum(n, vector<long long>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      sum[i][j] = b[i][j];
      if (i > 0) {
        sum[i][j] += sum[i - 1][j];
      }
      if (j > 0) {
        sum[i][j] += sum[i][j - 1];
      }
      if (i > 0 && j > 0) {
        sum[i][j] -= sum[i - 1][j - 1];
      }
    }
  }
  auto Query = [&](int x1, int y1, int x2, int y2) {
    long long res = sum[x2][y2];
    if (x1 > 0) {
      res -= sum[x1 - 1][y2];
    }
    if (y1 > 0) {
      res -= sum[x2][y1 - 1];
    }
    if (x1 > 0 && y1 > 0) {
      res += sum[x1 - 1][y1 - 1];
    }
    return res;
  };
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      ans = max(ans, Query(max(0, i - p + 1), max(0, j - p + 1), i, j));
    }
  }
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 100 / 100