Untitled

From Coral Hamster, 3 Years ago, written in Plain Text, viewed 263 times.
URL http://axuhongbo.top/paste/view/3eec2809 Embed
Download Paste or View Raw
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<algorithm>
  4. #include<vector>
  5. using namespace std;
  6. int c[5100010];
  7. int n,m;
  8. int id(int i,int j){
  9. return i*(m+2)+j;
  10. }
  11. struct node{
  12.  int x1,y1,x2,y2;
  13.  void in(){
  14.    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  15.  }
  16. };
  17. struct nod{
  18.  int x,y,val;
  19.  bool operator < (const nod &b)const{
  20.    if(x==b.x&&y==b.y){
  21.      return abs(val)>abs(b.val);
  22.    }
  23.    if(x==b.x)
  24.      return y<b.y;
  25.    return x<b.x;
  26.  }
  27. };
  28. vector<nod>vd[1100010];
  29. int bit[1100010];
  30. void add(int pos,int x){
  31.  while(pos<=m+1){
  32.    bit[pos]+=x;
  33.    pos+=pos&-pos;
  34.  }
  35. }
  36. int sum(int pos){
  37.  int Sum=0;
  38.  while(pos){
  39.    Sum+=bit[pos];
  40.    pos-=pos&-pos;
  41.  }
  42.  return Sum;
  43. }
  44. int main()
  45. {
  46.  int t,x;
  47.  scanf("%d%d%d",&n,&m,&t);
  48.  for(int i=1;i<=n;i++)
  49.    for(int j=1;j<=m;j++){
  50.      scanf("%d",&x);
  51.      vd[x].push_back(nod{i,j,0});
  52.    }
  53.  node now;
  54.  while(t--){
  55.    now.in();
  56.    int k;
  57.    scanf("%d",&k);
  58.    vd[k].push_back(nod{now.x1,now.y1,1});
  59.    vd[k].push_back(nod{now.x2+1,now.y2+1,1});
  60.    vd[k].push_back(nod{now.x1,now.y2+1,-1});
  61.    vd[k].push_back(nod{now.x2+1,now.y1,-1});
  62.    c[id(now.x1,now.y1)]++;
  63.    c[id(now.x2+1,now.y2+1)]++;
  64.    c[id(now.x1,now.y2+1)]--;
  65.    c[id(now.x2+1,now.y1)]--;
  66.  }
  67.  for(int i=1;i<=n;i++){
  68.    for(int j=1;j<=m;j++){
  69.      c[id(i,j)]+=c[id(i-1,j)]+c[id(i,j-1)]-c[id(i-1,j-1)];
  70.    }
  71.  }
  72.  int ans=0;
  73.  for(int i=0;i<=n*m;i++){
  74.    sort(vd[i].begin(),vd[i].end());
  75.    printf("i=%d\n",i);
  76.    for(int j=0;j<vd[i].size();j++){
  77.         printf("%d %d\n",vd[i][j].x,vd[i][j].y);
  78.      if(vd[i][j].val==0){
  79.        if(c[id(vd[i][j].x,vd[i][j].y)]==sum(vd[i][j].y))
  80.          ans++;
  81.          printf("success:%d %d\n",vd[i][j].x,vd[i][j].y);
  82.      }
  83.      else {
  84.        add(vd[i][j].y,vd[i][j].val);
  85.      }
  86.    }
  87.    for(int j=0;j<vd[i].size();j++)
  88.      if(vd[i][j].val)
  89.      add(vd[i][j].y,-vd[i][j].val);
  90.  }
  91.  printf("%d\n",n*m-ans);
  92.  return 0;
  93. }
  94.  
  95. 2 2 2
  96. 1 2
  97. 2 3
  98. 1 1 2 2  2
  99. 2 1 2 1 1
  100.  

Reply to "Untitled"

Here you can reply to the paste above

captcha