fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
  6. #else
  7. #define DEBUG(...) 6
  8. #endif
  9.  
  10. template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
  11. template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
  12. ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
  13. template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
  14. template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
  15. if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
  16.  
  17. template<typename T>
  18. struct BIT {
  19.     int n, lg;
  20.     vector<T> bit;
  21.  
  22.     BIT(int _n) : n(_n), lg(__lg(n)), bit(n + 1) {}
  23.  
  24.     BIT(const vector<T> &a) : n((int) a.size()), lg(__lg(n)), bit(n + 1) {
  25.         for (int i=1; i<=n; i++) {
  26.             bit[i] += a[i-1];
  27.             if (i + (i & -i) <= n)
  28.                 bit[i+(i&-i)] += bit[i];
  29.         }
  30.     }
  31.  
  32.     T query(int i) {
  33.         T ret = 0;
  34.         for (; i>0; i-=i&-i)
  35.             ret += bit[i];
  36.         return ret;
  37.     }
  38.  
  39.     T query(int l, int r) {
  40.         return query(r) - query(l-1);
  41.     }
  42.  
  43.     void update(int i, T val) {
  44.         for (; i<=n; i+=i&-i)
  45.             bit[i] += val;
  46.     }
  47.  
  48.     int kth(T k) {
  49.         int ret = 0;
  50.         for (int i=lg; i>=0; i--) {
  51.             ret += 1 << i;
  52.             if (ret <= n && bit[ret] < k)
  53.                 k -= bit[ret];
  54.             else
  55.                 ret -= 1 << i;
  56.         }
  57.         return ret + 1;
  58.     }
  59. };
  60.  
  61. struct SegmentTree {
  62.     int n;
  63.     vector<int> a, st, lazy;
  64.  
  65.     SegmentTree(int _n) : n(_n), st(4*n), lazy(4*n) {}
  66.  
  67.     SegmentTree(const vector<int> &_a) : n((int) _a.size()), a(_a), st(4*n), lazy(4*n) {
  68.         build(1, 0, n-1);
  69.     }
  70.  
  71.     void build(int p, int l, int r) {
  72.         if (l == r) {
  73.             st[p] += a[l];
  74.             return;
  75.         }
  76.         int m = (l + r) / 2;
  77.         build(2*p, l, m);
  78.         build(2*p+1, m+1, r);
  79.         st[p] = min(st[2*p], st[2*p+1]);
  80.     }
  81.  
  82.     void push(int p, int l, int r) {
  83.         if (lazy[p]) {
  84.             st[p] += lazy[p];
  85.             if (l != r) {
  86.                 lazy[2*p] += lazy[p];
  87.                 lazy[2*p+1] += lazy[p];
  88.             }
  89.             lazy[p] = 0;
  90.         }
  91.     }
  92.  
  93.     int query(int p, int l, int r, int i, int j) {
  94.         push(p, l, r);
  95.         if (i > r || j < l)
  96.             return INT_MAX;
  97.         if (i <= l && r <= j)
  98.             return st[p];
  99.         int m = (l + r) / 2;
  100.         return min(query(2*p, l, m, i, j), query(2*p+1, m+1, r, i, j));
  101.     }
  102.  
  103.     int query(int i, int j) {
  104.         return query(1, 0, n-1, i, j);
  105.     }
  106.  
  107.     void update(int p, int l, int r, int i, int j, int val) {
  108.         push(p, l, r);
  109.         if (i > r || j < l)
  110.             return;
  111.         if (i <= l && r <= j) {
  112.             st[p] += val;
  113.             if (l != r) {
  114.                 lazy[2*p] += val;
  115.                 lazy[2*p+1] += val;
  116.             }
  117.             return;
  118.         }
  119.         int m = (l + r) / 2;
  120.         update(2*p, l, m, i, j, val);
  121.         update(2*p+1, m+1, r, i, j, val);
  122.         st[p] = min(st[2*p], st[2*p+1]);
  123.     }
  124.  
  125.     void update(int i, int j, int val) {
  126.         update(1, 0, n-1, i, j, val);
  127.     }
  128. };
  129.  
  130. int main() {
  131.     ios_base::sync_with_stdio(false);
  132.     cin.tie(NULL);
  133.  
  134.     int t;
  135.     cin >> t;
  136.     for (int cn=1; cn<=t; cn++) {
  137.         int r, c, k, q;
  138.         cin >> r >> c >> k >> q;
  139.         k--;
  140.         vector<string> g(r);
  141.         vector<BIT<int>> bit(c, BIT<int>(r));
  142.         vector<set<int>> st(c);
  143.         for (int i=0; i<r; i++) {
  144.             cin >> g[i];
  145.             for (int j=0; j<c; j++)
  146.                 if (g[i][j] == 'X') {
  147.                     bit[j].update(i + 1, 1);
  148.                     st[j].insert(i);
  149.                 }
  150.         }
  151.         vector<pair<int, int>> queries;
  152.         for (int i=0; i<q; i++) {
  153.             int a, b;
  154.             cin >> a >> b;
  155.             a--, b--;
  156.             queries.emplace_back(a, b);
  157.         }
  158.  
  159.         // 0-based to 1-based
  160.         auto upd = [&] (int j, int i, int x) -> void {
  161.             bit[j].update(i + 1, x);
  162.         };
  163.  
  164.         auto query = [&] (int j, int l, int r) -> int {
  165.             return bit[j].query(l + 1, r + 1);
  166.         };
  167.  
  168.         auto shiz = [&] (int i) -> int {
  169.             return max(k - i, -1);
  170.         };
  171.  
  172.         // down shifts (use upper row)
  173.         // find clog point
  174.         // shift 0, 1, 2, ..., r times (might be r - 1 but whatever)
  175.         // if it's clogged at shift s, then all later shifts are guaranteed to have a car there
  176.         SegmentTree stDown(r + 1);
  177.         vector<int> cnt(c), clog(c, -1);
  178.         int tot = 0;
  179.         for (int j=0; j<c; j++) {
  180.             cnt[j] = query(j, k, r - 1);
  181.             if (cnt[j] == r - k)
  182.                 clog[j] = 0;
  183.             tot += g[k][j] == 'X';
  184.         }
  185.         // DEBUG("INIT", cn, cnt);
  186.         stDown.update(0, 0, tot);
  187.         for (int s=1; s<=r; s++) {
  188.             int tot = s;
  189.             for (int j=0; j<c; j++) {
  190.                 bool car = k - s >= 0 ? g[k-s][j] == 'X' : false;
  191.                 if (clog[j] == -1) {
  192.                     // shift one above
  193.                     if (car) {
  194.                         cnt[j]++;
  195.                         if (cnt[j] == r - k)
  196.                             clog[j] = s;
  197.                     }
  198.                 }
  199.                 tot += car || clog[j] != -1;
  200.             }
  201.             stDown.update(s, s, tot);
  202.         }
  203.         // DEBUG(cn, clog);
  204.  
  205.         // do the updates for the down shifts
  206.         vector<int> ret(q, INT_MAX);
  207.         vector<string> old = g;
  208.         for (int i=0; i<q; i++) {
  209.             auto [a, b] = queries[i];
  210.             int yyyy = shiz(a);
  211.             if (g[a][b] == 'X') {
  212.                 // remove car
  213.                 // clog point could move up
  214.                 g[a][b] = '.';
  215.                 st[b].erase(a);
  216.                 upd(b, a, -1);
  217.                 if (clog[b] != -1 && yyyy <= clog[b]) {
  218.                     // DEBUG("REM", cn, a, b, clog[b], st[b]);
  219.                     if (cn == 6) DEBUG(yyyy);
  220.                     if (yyyy != -1) stDown.update(yyyy, yyyy, -1);
  221.                     stDown.update(clog[b] + 1, r, -1);
  222.                     auto it = st[b].lower_bound(k - clog[b]);
  223.                     if (it == st[b].begin()) {
  224.                         // no clog point
  225.                         clog[b] = -1;
  226.                     } else {
  227.                         // yes clog point
  228.                         clog[b] = shiz(*prev(it));
  229.                         stDown.update(clog[b], r, 1);
  230.                     }
  231.                     // DEBUG(clog[b]);
  232.                 } else if (clog[b] == -1) {
  233.                     if (yyyy != -1) stDown.update(yyyy, yyyy, -1);
  234.                 }
  235.             } else {
  236.                 // insert car
  237.                 // clog point could move down
  238.                 g[a][b] = 'X';
  239.                 st[b].insert(a);
  240.                 upd(b, a, 1);
  241.                 if (clog[b] != -1 && yyyy < clog[b]) {
  242.                     // DEBUG("INS", cn, a, b, clog[b]);
  243.                     if (yyyy != -1) stDown.update(yyyy, yyyy, 1);
  244.                     stDown.update(clog[b], r, -1);
  245.                     auto it = next(st[b].find(k - clog[b]));
  246.                     // yes clog point
  247.                     clog[b] = shiz(*it);
  248.                     stDown.update(clog[b] + 1, r, 1);
  249.                 } else if (clog[b] == -1 && (int) st[b].size() >= r - k) {
  250.                     // DEBUG("PP?");
  251.                     int pp = bit[b].kth((int) st[b].size() - (r - k) + 1) - 1;
  252.                     DEBUG(i, pp);
  253.                     int cnt = query(b, pp, r - 1);
  254.                     DEBUG(cnt);
  255.                     if (cnt == r - k) {
  256.                         // clog point
  257.                         clog[b] = shiz(pp);
  258.                         stDown.update(clog[b] + (clog[b] != yyyy), r, 1);
  259.                         DEBUG(clog[b]);
  260.                         if (yyyy < clog[b] && yyyy != -1) stDown.update(yyyy, yyyy, 1);
  261.                     }
  262.                 } else if (clog[b] == -1) {
  263.                     if (yyyy != -1) stDown.update(yyyy, yyyy, 1);
  264.                 }
  265.             }
  266.             if (cn == 6) DEBUG(cn, i, a, b, st[b], clog);
  267.             // DEBUG(stDown.query(0, r));
  268.             // for (int i=0; i<=r; i++)
  269.             //     DEBUG(i, stDown.query(i, i));
  270.             ret[i] = min(ret[i], stDown.query(0, r));
  271.         }
  272.  
  273.         // holy fuck do the same thing with up shift kill me please
  274.         // check rows below
  275.         {
  276.             vector<BIT<int>> bit(c, BIT<int>(r));
  277.             vector<set<int>> st(c);
  278.             g = old;
  279.             for (int i=0; i<r; i++) {
  280.                 // cin >> g[i];
  281.                 for (int j=0; j<c; j++)
  282.                     if (g[i][j] == 'X') {
  283.                         bit[j].update(i + 1, 1);
  284.                         st[j].insert(i);
  285.                     }
  286.             }
  287.  
  288.             // 0-based to 1-based
  289.         auto upd = [&] (int j, int i, int x) -> void {
  290.             bit[j].update(i + 1, x);
  291.         };
  292.  
  293.         auto query = [&] (int j, int l, int r) -> int {
  294.             return bit[j].query(l + 1, r + 1);
  295.         };
  296.  
  297.             auto blah = [&] (int i) -> int {
  298.                 return max(i - k, -1);
  299.             };
  300.  
  301.             SegmentTree stDown(r + 1);
  302.             vector<int> cnt(c), clog(c, -1);
  303.             int tot = 0;
  304.             for (int j=0; j<c; j++) {
  305.                 cnt[j] = query(j, 0, k);
  306.                 if (cnt[j] == k + 1)
  307.                     clog[j] = 0;
  308.                 tot += g[k][j] == 'X';
  309.             }
  310.             // DEBUG("INIT", cn, cnt);
  311.             stDown.update(0, 0, tot);
  312.             for (int s=1; s<=r; s++) {
  313.                 int tot = s;
  314.                 for (int j=0; j<c; j++) {
  315.                     bool car = k + s < r ? g[k+s][j] == 'X' : false;
  316.                     if (clog[j] == -1) {
  317.                         // shift one above
  318.                         if (car) {
  319.                             cnt[j]++;
  320.                             if (cnt[j] == k + 1)
  321.                                 clog[j] = s;
  322.                         }
  323.                     }
  324.                     tot += car || clog[j] != -1;
  325.                 }
  326.                 stDown.update(s, s, tot);
  327.             }
  328.             if (cn == 5) DEBUG(cn, clog);
  329.  
  330.             // do the updates for the up shifts
  331.             for (int i=0; i<q; i++) {
  332.                 auto [a, b] = queries[i];
  333.                 int yyyy = blah(a);
  334.                 if (g[a][b] == 'X') {
  335.                     // remove car
  336.                     // clog point could move down
  337.                     g[a][b] = '.';
  338.                     st[b].erase(a);
  339.                     upd(b, a, -1);
  340.                     if (clog[b] != -1 && yyyy <= clog[b]) {
  341.                         if (cn == 5) DEBUG("REM", cn, a, b, yyyy, clog[b], st[b]);
  342.                         if (yyyy != -1) stDown.update(yyyy, yyyy, -1);
  343.                         stDown.update(clog[b] + 1, r, -1);
  344.                         auto it = st[b].upper_bound(k + clog[b]);
  345.                         if (cn == 5) DEBUG(st[b]);
  346.                         if (it == st[b].end()) {
  347.                             // no clog point
  348.                             if (cn == 5) DEBUG("NONONO");
  349.                             clog[b] = -1;
  350.                         } else {
  351.                             // yes clog point
  352.                             clog[b] = blah(*(it));
  353.                             stDown.update(clog[b], r, 1);
  354.                         }
  355.                         // DEBUG(clog[b]);
  356.                     } else if (clog[b] == -1) {
  357.                         if (yyyy != -1) stDown.update(yyyy, yyyy, -1);
  358.                     }
  359.                 } else {
  360.                     // insert car
  361.                     // clog point could move down
  362.                     g[a][b] = 'X';
  363.                     st[b].insert(a);
  364.                     upd(b, a, 1);
  365.                     DEBUG("HEY", yyyy);
  366.                     if (clog[b] != -1 && yyyy < clog[b]) {
  367.                         // DEBUG("INS", cn, a, b, clog[b]);
  368.                         if (yyyy != -1) stDown.update(yyyy, yyyy, 1);
  369.                         stDown.update(clog[b], r, -1);
  370.                         auto it = prev(st[b].find(k + clog[b]));
  371.                         // yes clog point
  372.                         clog[b] = blah(*it);
  373.                         stDown.update(clog[b] + 1, r, 1);
  374.                     } else if (clog[b] == -1 && (int) st[b].size() >= k + 1) {
  375.                         DEBUG(i, "PP?");
  376.                         int pp = bit[b].kth(k + 1) - 1;
  377.                         // DEBUG(pp, r, k + 1, st[b].size(), st[b]);
  378.                         // for (int j=0; j<r; j++)
  379.                         //     DEBUG(bit[j].query(j + 1, j + 1));
  380.                         int cnt = query(b, 0, pp);
  381.                         // DEBUG(cnt);
  382.                         if (cnt == k + 1) {
  383.                             // clog point
  384.                             clog[b] = blah(pp);
  385.                             stDown.update(clog[b] + (clog[b] != yyyy), r, 1);
  386.                             DEBUG(clog[b]);
  387.                             DEBUG(stDown.query(0, 0));
  388.                             if (yyyy < clog[b] && yyyy != -1) stDown.update(yyyy, yyyy, 1);
  389.                         }
  390.                     } else if (clog[b] == -1) {
  391.                         if (yyyy != -1) stDown.update(yyyy, yyyy, 1);
  392.                     }
  393.                 }
  394.                 // DEBUG(cn, i, a, b, st[b], clog[b]);
  395.                 DEBUG(i, stDown.query(0, r));
  396.                     for (int i=0; i<=r; i++)
  397.                         DEBUG(i, stDown.query(i, i));
  398.                 DEBUG(clog);
  399.                 ret[i] = min(ret[i], stDown.query(0, r));
  400.             }
  401.         }
  402.  
  403.         DEBUG(cn, ret);
  404.         cout << "Case #" << cn << ": " << accumulate(ret.begin(), ret.end(), 0LL) << "\n";
  405.     }
  406.  
  407.     return 0;
  408. }
  409.  
Success #stdin #stdout 0s 5632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iv4U5d
language:
C++14 (gcc 8.3)
created:
3 years 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!