CODE_tmp

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

Reply to "CODE_tmp"

Here you can reply to the paste above

captcha