oj.uz

Submission #132407

# Submission time Handle Problem Language Result Execution time Memory
132407 2019-07-18T19:41:36 Z dragonslayerit Pyramid Base (IOI08_pyramid_base) C++14
0 / 100
 5000 ms 110348 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;

int 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,int 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);
  }
}

int 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<lastx;x++){
    for(auto a:at[x]){
      update(1,0,ST_SIZE,0,a.first,a.second);
    }
    int cost=query(1,0,ST_SIZE,0,lasty-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<lastx-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;
  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 19 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 19600 KB Output isn't correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3496 ms 34628 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 5036 ms 39732 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 5020 ms 40596 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 5010 ms 40784 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 5023 ms 88128 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 5015 ms 98100 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 5017 ms 110348 KB Time limit exceeded
2 Halted 0 ms 0 KB -