oj.uz

Submission #132422

# Submission time Handle Problem Language Result Execution time Memory
132422 2019-07-18T19:56:03 Z dragonslayerit Pyramid Base (IOI08_pyramid_base) C++14
0 / 100
 5000 ms 107676 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 19192 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 19320 KB Output isn't correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 19572 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 19912 KB Output isn't correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 20088 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 20184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 357 ms 20684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 459 ms 22292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3719 ms 34480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5022 ms 39468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5079 ms 40516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5026 ms 40360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 86656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 94812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 107676 KB Time limit exceeded
2 Halted 0 ms 0 KB -