fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 1005;
  6. const int MAXM = 1000005;
  7. const int INF = 1e9;
  8. int n, q;
  9. string as[MAXN];
  10. int dy[MAXN][MAXN];
  11. int cnt[MAXM];
  12. int tree[4 * MAXM];
  13. int lazy[4 * MAXM];
  14. int max_d = 1;
  15. int total_forts = 0;
  16.  
  17. void push(int v) {
  18.     if (lazy[v] != 0) {
  19.         lazy[2 * v] += lazy[v];
  20.         tree[2 * v] += lazy[v];
  21.         lazy[2 * v + 1] += lazy[v];
  22.         tree[2 * v + 1] += lazy[v];
  23.         lazy[v] = 0;
  24.     }
  25. }
  26.  
  27. void build(int v, int l, int r) {
  28.     tree[v] = -INF;
  29.     lazy[v] = 0;
  30.     if (l == r) return;
  31.     int mid = (l + r) / 2;
  32.     build(2 * v, l, mid);
  33.     build(2 * v + 1, mid + 1, r);
  34. }
  35.  
  36. void update_range(int v, int l, int r, int ql, int qr, int val) {
  37.     if (ql > r || qr < l) return;
  38.     if (ql <= l && r <= qr) {
  39.         tree[v] += val;
  40.         lazy[v] += val;
  41.         return;
  42.     }
  43.     push(v);
  44.     int mid = (l + r) / 2;
  45.     update_range(2 * v, l, mid, ql, qr, val);
  46.     update_range(2 * v + 1, mid + 1, r, ql, qr, val);
  47.     tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  48. }
  49.  
  50. void set_active(int v, int l, int r, int pos, bool active) {
  51.     if (l == r) {
  52.         if (active) tree[v] = pos - 1 + lazy[v];
  53.         else tree[v] = -INF;
  54.         return;
  55.     }
  56.     push(v);
  57.     int mid = (l + r) / 2;
  58.     if (pos <= mid) set_active(2 * v, l, mid, pos, active);
  59.     else set_active(2 * v + 1, mid + 1, r, pos, active);
  60.     tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  61. }
  62.  
  63. void add_fort(int d) {
  64.     if (d <= 0) return;
  65.     total_forts++;
  66.     cnt[d]++;
  67.     if (cnt[d] == 1) {
  68.         set_active(1, 1, max_d, d, true);
  69.     }
  70.     update_range(1, 1, max_d, 1, d, 1);
  71. }
  72.  
  73. void remove_fort(int d) {
  74.     if (d <= 0) return;
  75.     total_forts--;
  76.     cnt[d]--;
  77.     update_range(1, 1, max_d, 1, d, -1);
  78.     if (cnt[d] == 0) {
  79.         set_active(1, 1, max_d, d, false);
  80.     }
  81. }
  82.  
  83. int odp() {
  84.     if (total_forts == 0) return 0;
  85.     return tree[1];
  86. }
  87.  
  88. int main() {
  89.     ios_base::sync_with_stdio(0);
  90.     cin.tie(0);
  91.    cin>>n>>q;
  92.  
  93.     for (int i = 0; i < n; i++) {
  94.         cin >> as[i];
  95.     }
  96.  
  97.     for (int i = 0; i < n; i++) {
  98.         for (int j = 0; j < n; j++) {
  99.             dy[i][j] = -1;
  100.         }
  101.     }
  102.  
  103.     queue<pair<int, int>> q_bfs;
  104.     dy[0][0] = 0;
  105.     q_bfs.push({0, 0});
  106.  
  107.     int dr[] = {-1, 1, 0, 0};
  108.     int dc[] = {0, 0, -1, 1};
  109.  
  110.     while (!q_bfs.empty()) {
  111.         int r = q_bfs.front().first;
  112.         int c = q_bfs.front().second;
  113.         q_bfs.pop();
  114.  
  115.         max_d = max(max_d, dy[r][c]);
  116.  
  117.         for (int i = 0; i < 4; i++) {
  118.             int nr = r + dr[i];
  119.             int nc = c + dc[i];
  120.             if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
  121.                 if (as[nr][nc] != '#' && dy[nr][nc] == -1) {
  122.                     dy[nr][nc] = dy[r][c] + 1;
  123.                     q_bfs.push({nr, nc});
  124.                 }
  125.             }
  126.         }
  127.     }
  128.  
  129.     build(1, 1, max_d);
  130.  
  131.     for (int i = 0; i < n; i++) {
  132.         for (int j = 0; j < n; j++) {
  133.             if (as[i][j] == 'F') {
  134.                 add_fort(dy[i][j]);
  135.             }
  136.         }
  137.     }
  138.  
  139.     cout << odp() << "\n";
  140.  
  141.     for (int i = 0; i < q; i++) {
  142.         int r, c;
  143.         cin >> r >> c;
  144.         r--; c--;
  145.         int d = dy[r][c];
  146.  
  147.         if (as[r][c] == 'F') {
  148.             as[r][c] = '.';
  149.             remove_fort(d);
  150.         } else {
  151.             as[r][c] = 'F';
  152.             add_fort(d);
  153.         }
  154.  
  155.         cout << odp() << "\n";
  156.     }
  157.  
  158.     return 0;
  159. }
Success #stdin #stdout 0s 7700KB
comments (?)
stdin 
4 3
Z...
###.
F.#F
...F
3 2
4 1
3 1
stdout 
10
10
11
10
https://ideone.com/zwcEt8
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!