fork download
copy 
  1. /* Author haleyk10198 */
  2. /* �@��:  haleyk10198 */
  3. /* CF handle: haleyk100198*/
  4. #include <bits/stdc++.h>
  5.  
  6. #define MOD 1000000007
  7. #define LINF (1LL<<60)
  8. #define INF 2147483647
  9. #define PI 3.1415926535897932384626433
  10. #define ll long long
  11. #define pii pair<int,int>
  12. #define pb push_back
  13. #define mp(x,y) make_pair((x),(y))
  14.  
  15. using namespace std;
  16.  
  17. string itos(int x){
  18.     stringstream ss;
  19.     ss << x;
  20.     return ss.str();
  21. }
  22.  
  23. int n, m, qu, b[10][100010];
  24. vector<pii> e[10][4], con;
  25. int vis[10][4];
  26.  
  27. queue<pii> q;
  28. int fr, ff;
  29. vector<pii> E[401100][10][2];
  30.  
  31. struct node{
  32.     int Err;
  33.     int res, isnull, cccon, lpos, rpos;
  34.     node(){
  35.         isnull = false;
  36.         res = cccon = lpos = rpos = 0;
  37.     }
  38. };
  39.  
  40. node res;
  41.  
  42. node merge(node lhs, node rhs){
  43.     res.Err = fr++;
  44.     res.res = res.isnull = res.cccon = res.lpos = res.rpos = 0;
  45.     if(lhs.isnull)
  46.         return rhs;
  47.     if(rhs.isnull)
  48.         return lhs;
  49.     memset(vis, 0, sizeof(vis));
  50.     res.lpos = lhs.lpos, res.rpos = rhs.rpos;
  51.     for(int i = 0; i < n; i++)
  52.         for(int j = 0; j < 2; j++){
  53.             E[res.Err][i][j].clear();
  54.             e[i][j] = E[lhs.Err][i][j];
  55.             e[i][j+2] = E[rhs.Err][i][j];
  56.             for(auto &x: e[i][j+2])
  57.                 x.second += 2;
  58.         }
  59.     for(int i = 0; i < n; i++)
  60.         if(b[i][lhs.rpos] == b[i][rhs.lpos])
  61.             e[i][1].pb(mp(i, 2)), e[i][2].pb(mp(i, 1));
  62.     for(int i = 0; i < n; i++){
  63.         for(int j = 0; j < 4; j++)
  64.         if(not vis[i][j]){
  65.             res.res++;
  66.             int f = 1;
  67.             while(q.size())
  68.                 q.pop();
  69.             con.clear();
  70.             q.push(mp(i, j));
  71.             while(q.size()){
  72.                 int x = q.front().first;
  73.                 int y = q.front().second;
  74.                 q.pop();
  75.                 if(vis[x][y])
  76.                     continue;
  77.                 vis[x][y] = true;
  78.                 for(auto i: e[x][y])
  79.                     q.push(i);
  80.                 if(y == 0 || y == 3){
  81.                     con.pb(mp(x, y/3)); 
  82.                     if(f)
  83.                         res.cccon++, f = 0;
  84.                 }           
  85.             }
  86.             for(int i = 0; i+1 < con.size(); i++)
  87.                 E[res.Err][con[i].first][con[i].second].pb(mp(con[i+1].first, con[i+1].second)), E[res.Err][con[i+1].first][con[i+1].second].pb(mp(con[i].first, con[i].second));
  88.         }
  89.     }
  90.     res.res += lhs.res+rhs.res-lhs.cccon-rhs.cccon;
  91.     return res;
  92. }
  93.  
  94. node T[400010], a[100010];
  95.  
  96. void build(int l = 0, int r = m, int pos = 1){
  97.     if(l+1 == r){
  98.         T[pos] = a[l];
  99.         // cout << T[pos].Err << ' ';
  100.         return;
  101.     }
  102.     int mid = (l+r)/2;
  103.     build(l, mid, pos*2);
  104.     build(mid, r, pos*2+1);
  105.     T[pos].Err = fr++;
  106.     T[pos] = merge(T[pos*2], T[pos*2+1]);
  107.     return;
  108. }
  109.  
  110. node ask(int l, int r, int x = 0, int y = m, int pos = 1){
  111.     if(x >= r || l >= y){
  112.         node res;
  113.         res.Err = fr++;
  114.         res.isnull = true;
  115.         return res;
  116.     }
  117.     if(l <= x && r >= y)
  118.         return T[pos];
  119.     int mid = (x+y)/2;
  120.     return merge(ask(l, r, x, mid, pos*2), ask(l, r, mid, y, pos*2+1));
  121. }
  122.  
  123. int main(){
  124.     // freopen("input.txt","r",stdin);
  125.     //freopen("output.txt","w",stdout);
  126.     ios_base::sync_with_stdio(false);
  127.     cin >> n >> m >> qu;
  128.     for(int i = 0; i < n; i++)
  129.         for(int j = 0; j < m; j++)
  130.             cin >> b[i][j];
  131.     for(int i = 0; i < n; i++)
  132.         for(int j = 0; j < m; j++){
  133.             a[j].Err = j;
  134.             E[j][i][0].pb(mp(i, 1)), E[j][i][1].pb(mp(i, 0));
  135.             if(i+1 == n){
  136.                 a[j].res += n;
  137.                 a[j].cccon = a[j].res;
  138.                 a[j].lpos = a[j].rpos = j;
  139.                 continue;
  140.             }
  141.             if(b[i+1][j] == b[i][j])
  142.                 E[j][i][0].pb(mp(i+1, 0)), E[j][i+1][0].pb(mp(i, 0)), a[j].res--;
  143.         }
  144.     fr = m;
  145.     build();
  146.     ff = fr;
  147.     while(qu--){
  148.         fr = ff;
  149.         int l, r;
  150.         cin >> l >> r;
  151.         cout << ask(--l, r).res << endl;
  152.     }
  153.     return 0;
  154. }
Time limit exceeded #stdin #stdout 5s 8093696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jXHtFT
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!