fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  4. #define ROF(i,a,b) for(int i=a;i>=b;i--)
  5. #define pi pair<int,int>
  6. #define pii pair<int,pi>
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. #define all(x) x.begin(), x.end()
  11. #define sz(a) (int) a.size()
  12. #define endl '\n'
  13. #define data "board"
  14.  
  15. using namespace std;
  16. const ll linf = 1e18;
  17. const int inf = 1e9;
  18. const int MOD = 1e7 + 1203, N = 1600;
  19.  
  20. void add(int &a, int b)
  21. {
  22.     a += b;
  23.     if(a>=MOD)
  24.         a-=MOD;
  25.     if(a<0)
  26.         a += MOD;
  27. }
  28.  
  29. int modulo(int x)
  30. {
  31.     if(x<=1)
  32.         return 1;
  33.     return (MOD - MOD/x) * modulo(MOD/x) % MOD;
  34. }
  35.  
  36. int mul(int a, int b)
  37. {
  38.     return (1ll *a * b) % MOD;
  39. }
  40.  
  41. int n, m, q;
  42. char a[N+3][N+3];
  43. int h[N+3];
  44. int L[N+3], R[N+3];
  45. int div2;
  46.  
  47. void inp(void)
  48. {
  49.     cin >> n >> m >> q;
  50.     FOR(i, 1, n)
  51.     {
  52.         FOR(j, 1, m) cin >> a[i][j];
  53.     }
  54. }
  55.  
  56. int pw(int a, int b)
  57. {
  58.     int ret = 1;
  59.     while(b > 0)
  60.     {
  61.         if(b & 1) ret = mul(ret, a);
  62.         a = mul(a, a);
  63.         b >>= 1;
  64.     }
  65.     return ret;
  66. }
  67.  
  68. ll calc(void)
  69. {
  70.     FOR(j, 1, m) h[j] = 0;
  71.     ll ret = 0;
  72.  
  73.     FOR(i, 1, n)
  74.     {
  75.         stack<int> st;
  76.         st.push(0);
  77.         FOR(j, 1, m) L[j] = R[j] = j;
  78.  
  79.         FOR(j, 1, m)
  80.         {
  81.             if(a[i][j] == '.') h[j] = 0;
  82.             else ++h[j];
  83.  
  84.             while(!st.empty() && h[st.top()] >= h[j])
  85.             {
  86.                 L[j] = L[st.top()];
  87.                 st.pop();
  88.             }
  89.             st.push(j);
  90.         }
  91.  
  92.         while(!st.empty()) st.pop();
  93.         st.push(m+1);
  94.  
  95.         ROF(j, m, 1)
  96.         {
  97.             while(!st.empty() && h[st.top()] > h[j])
  98.             {
  99.                 R[j] = R[st.top()];
  100.                 st.pop();
  101.             }
  102.             st.push(j);
  103.  
  104.             int lenR = R[j] - j + 1;
  105.             int lenL = j - L[j] + 1;
  106.             ll sumR = 1ll * lenR * (j+1 + R[j]+1) / 2;
  107.             ll sumL = 1ll * lenL * (L[j] + j) / 2;
  108.             ll tmp = 1ll * lenL * sumR - 1ll * lenR * sumL;
  109.             tmp *= (1ll * h[j] * (h[j] + 1)) / 2;
  110.             ret += tmp;
  111.         }
  112.     }
  113.  
  114.     return ret;
  115. }
  116.  
  117. void solve(void)
  118. {
  119.     h[0] = h[m+1] = -inf;
  120.     div2 = pw(2, MOD - 2);
  121.     cout << calc() % MOD << ' ';
  122.     FOR(_, 1, q)
  123.     {
  124.         int x1, x2, y1, y2; cin >> x1 >> x2 >> y1 >> y2;
  125.         FOR(i, x1, x2)
  126.         {
  127.             FOR(j, y1, y2) a[i][j] = 'X';
  128.         }
  129.         cout << calc() % MOD << ' ';
  130.     }
  131. }
  132.  
  133. signed main()
  134. {
  135.     ios_base::sync_with_stdio(0);
  136.     cin.tie(0); cout.tie(0);
  137.  
  138.     if(fopen(data".inp", "r"))
  139.     {
  140.         freopen(data".inp","r",stdin);
  141.         freopen(data".out","w",stdout);
  142.     }
  143.  
  144.     inp();
  145.     solve();
  146.     return 0;
  147. }
  148.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/rVhPz1
language:
C++14 (clang 8.0)
created:
3 days 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!