Submission #132422

#	Time	Username	Problem	Language	Result	Execution time	Memory
132422		dragonslayerit	Pyramid Base (IOI08_pyramid_base)	C++14	0 / 100	5079 ms	107676 KiB

pyramid_base

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

const long long INF=1e10+7;

struct Obstacle{
  int x1,y1,x2,y2,c;
  void read(){
    scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&c);
    x1--,y1--;
  }
}obstacles[400005];
int M,N,B,P;

std::vector<std::pair<int,int> > at[800005];

const int ST_SIZE=1<<20;

long long st[ST_SIZE*2],lazy[ST_SIZE*2];

void push(int w,int L,int R){
  if(R-L>1){
    lazy[w<<1]+=lazy[w];
    lazy[w<<1|1]+=lazy[w];
  }
  st[w]+=lazy[w];
  lazy[w]=0;
}

void pull(int w,int L,int R){
  st[w]=std::min(st[w<<1],st[w<<1|1]);
}

void update(int w,int L,int R,int a,int b,long long v){
  push(w,L,R);
  if(a>=R||b<=L) return;
  if(a<=L&&b>=R){
    lazy[w]+=v;
    push(w,L,R);
  }else{
    int M=(L+R)/2;
    update(w<<1,L,M,a,b,v);
    update(w<<1|1,M,R,a,b,v);
    pull(w,L,R);
  }
}

long long query(int w,int L,int R,int a,int b){
  push(w,L,R);
  if(a>=R||b<=L) return INF;
  if(a<=L&&b>=R){
    return st[w];
  }else{
    int M=(L+R)/2;
    return std::min(query(w<<1,L,M,a,b),query(w<<1|1,M,R,a,b));
  }
}

bool check(int shrink){
  std::map<int,int> cpsx,cpsy;
  cpsx[0],cpsy[0];
  cpsx[M-shrink],cpsy[N-shrink];
  auto clampx=[=](int x){return std::max(0,std::min(x,M-shrink));};
  auto clampy=[=](int y){return std::max(0,std::min(y,N-shrink));};
  for(int i=0;i<P;i++){
    const Obstacle& ob=obstacles[i];
    int x1=clampx(ob.x1-shrink),y1=clampy(ob.y1-shrink);
    int x2=clampx(ob.x2),y2=clampy(ob.y2);
    cpsx[x1],cpsx[x2];
    cpsy[y1],cpsy[y2];
  }
  {
    int lastx=0,lasty=0;
    for(auto& it:cpsx){
      it.second=lastx++;
    }
    for(auto& it:cpsy){
      it.second=lasty++;
    }
  }
  //printf("Field: [%d,%d]x[%d,%d]\n",0,cpsx[M-shrink],0,cpsy[N-shrink]);
  for(int i=0;i<P;i++){
    const Obstacle& ob=obstacles[i];
    int x1=cpsx[clampx(ob.x1-shrink)],y1=cpsy[clampy(ob.y1-shrink)];
    int x2=cpsx[clampx(ob.x2)],y2=cpsy[clampy(ob.y2)];
    int c=ob.c;
    at[x1].push_back({y2,c});
    at[x1].push_back({y1,-c});
    at[x2].push_back({y2,-c});
    at[x2].push_back({y1,c});
    //printf("obstacle [%d,%d]x[%d,%d] cost %d\n",x1,x2,y1,y2,c);
  }
  bool good=false;
  for(int x=0;x<=cpsx[M-shrink];x++){
    for(auto a:at[x]){
      update(1,0,ST_SIZE,0,a.first,a.second);
    }
    long long cost=query(1,0,ST_SIZE,0,cpsy[N-shrink]);
    /*
    printf("base=%d,x'=%d: cost=%d\n",base,x,cost);
    for(int y=0;y<lasty-1;y++){
      printf("%d ",query(1,0,ST_SIZE,y,y+1));
    }
    printf("\n");
    */
    if(x<cpsx[M-shrink]&&cost<=B){
      good=true;
    }
  }
  return good;
}

int main(){
  scanf("%d %d",&M,&N);
  scanf("%d %d",&B,&P);
  for(int i=0;i<P;i++){
    obstacles[i].read();
  }
  int low=0,high=N;//M+N+1;
  while(high-low>1){
    int mid=(low+high)/2;
    if(check(mid-1)){
      low=mid;
    }else{
      high=mid;
    }
  }
  printf("%d\n",low);
  return 0;
}  

Compilation message (stderr)

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&M,&N);
   ~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&B,&P);
   ~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp: In member function 'void Obstacle::read()':
pyramid_base.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10