Submission #7421

#	Time	Username	Problem	Language	Result	Execution time	Memory
7421		gs13068	수족관 2 (KOI13_aqua2)	C++98	100 / 100	172 ms	36896 KiB

aqua2

#include<cstdio>
#include<algorithm>

struct tree
{
  int x;
  int y;
} tr[1000000];

int x[200000];
int y[200000];
int z[200000];

void init()
{
  int i;
  for(i=0;i<1000000;i++)
  {
    tr[i].x=1e9;
    tr[i].y=i-262144;
  }
}

void update(int x,int y)
{
  x+=262144;
  tr[x].x=y;
  while(x)
  {
    if(tr[x>>1].x>y)
    {
      tr[x>>1].x=y;
      tr[x>>1].y=tr[x].y;
    }
    x>>=1;
  }
}

int where(int x,int y)
{
  int r=1e9,ri;
  x+=262144;
  y+=262144;
  while(x<=y)
  {
    if(tr[x].x<r)
    {
      r=tr[x].x;
      ri=tr[x].y;
    }
    if(tr[y].x<r)
    {
      r=tr[y].x;
      ri=tr[y].y;
    }
    x=(x+1)>>1;
    y=(y-1)>>1;
  }
  return ri;
}

std::pair<std::pair<int,double>,long long> dfs(int l,int r,int d)
{
  if(l>r)return std::make_pair(std::make_pair(0,0.0),0LL);
  if(l==r)
  {
    if(z[l])return std::make_pair(std::make_pair(1,1.*(x[r+1]-x[l])*(y[l]-d)),0LL);
    return std::make_pair(std::make_pair(0,0.0),1LL*(x[r+1]-x[l])*(y[l]-d));
  }
  std::pair<std::pair<int,double>,long long> res,ll,rr;
  int mid=where(l,r),cnt;
  ll=dfs(l,mid-1,y[mid]);
  rr=dfs(mid+1,r,y[mid]);
  res.first.first=ll.first.first+rr.first.first+z[mid];
  res.first.second=std::max(ll.first.second,rr.first.second);
  res.second=ll.second+rr.second;
  if(res.first.first)res.first.second+=1.*(x[r+1]-x[l])*(y[mid]-d)/res.first.first;
  else res.second+=1LL*(x[r+1]-x[l])*(y[mid]-d);
  return res;
}

int main()
{
  std::pair<std::pair<int,double>,long long> p;
  int i,n,m;
  scanf("%d",&n);
  n>>=1;
  n--;
  init();
  for(i=0;i<=n;i++)
  {
    scanf("%*d%*d%d%d",&x[i],&y[i]);
    update(i,y[i]);
  }
  scanf("%d",&m);
  while(m--)
  {
    scanf("%d%*d%*d%*d",&i);
    z[std::lower_bound(x,x+n,i)-x]=1;
  }
  p=dfs(0,n-1,0);
  printf("%.2lf\n%lld",p.first.second,p.second);
}

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 35 / 35
• Subtask 4: 31 / 31