oj.uz

Submission #132415

# Submission time Handle Problem Language Result Execution time Memory
132415 2019-07-18T19:45:43 Z dragonslayerit Pyramid Base (IOI08_pyramid_base) C++14
0 / 100
 5000 ms 102896 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

const int INF=1e9+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 base){
  std::map<int,int> cpsx,cpsy;
  cpsx[0],cpsy[0];
  cpsx[M-base+1],cpsy[N-base+1];
  auto clampx=[=](int x){return std::max(0,std::min(x,M-base+1));};
  auto clampy=[=](int y){return std::max(0,std::min(y,N-base+1));};
  for(int i=0;i<P;i++){
    int x1=clampx(obstacles[i].x1-base+1),y1=clampy(obstacles[i].y1-base+1);
    int x2=clampx(obstacles[i].x2),y2=clampy(obstacles[i].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,lastx,0,lasty);
  for(int i=0;i<P;i++){
    int x1=cpsx[clampx(obstacles[i].x1-base+1)],y1=cpsy[clampy(obstacles[i].y1-base+1)];
    int x2=cpsx[clampx(obstacles[i].x2)],y2=cpsy[clampy(obstacles[i].y2)];
    int c=obstacles[i].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-base+1];x++){
    for(auto a:at[x]){
      update(1,0,ST_SIZE,0,a.first,a.second);
    }
    int cost=query(1,0,ST_SIZE,0,cpsy[N-base+1]);
    /*
    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-base+1]&&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)){
      low=mid;
    }else{
      high=mid;
    }
  }
  printf("%d\n",low);
  return 0;
}

Compilation message

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:112: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:113: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 21 ms 19192 KB Output isn't correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3626 ms 34396 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 5035 ms 39472 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 5101 ms 40476 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 5053 ms 40224 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 5033 ms 86788 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 5101 ms 94744 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 5086 ms 102896 KB Time limit exceeded
2 Halted 0 ms 0 KB -