oj.uz

Submission #7421

# Submission time Handle Problem Language Result Execution time Memory
7421 2014-08-05T05:42:33 Z gs13068 수족관 2 (KOI13_aqua2) C++
100 / 100
 172 ms 36896 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11244 KB Output is correct
2 Correct 0 ms 11244 KB Output is correct
3 Correct 0 ms 11244 KB Output is correct
4 Correct 0 ms 11244 KB Output is correct
5 Correct 0 ms 11244 KB Output is correct
6 Correct 4 ms 11244 KB Output is correct
7 Correct 0 ms 11244 KB Output is correct
8 Correct 4 ms 11244 KB Output is correct
9 Correct 0 ms 11244 KB Output is correct
10 Correct 0 ms 11244 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11244 KB Output is correct
2 Correct 4 ms 11244 KB Output is correct
3 Correct 0 ms 11244 KB Output is correct
4 Correct 0 ms 11244 KB Output is correct
5 Correct 0 ms 11244 KB Output is correct
6 Correct 0 ms 11244 KB Output is correct
7 Correct 0 ms 11244 KB Output is correct
8 Correct 0 ms 11244 KB Output is correct
9 Correct 0 ms 11244 KB Output is correct
10 Correct 0 ms 11244 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11244 KB Output is correct
2 Correct 0 ms 11244 KB Output is correct
3 Correct 0 ms 11244 KB Output is correct
4 Correct 0 ms 11244 KB Output is correct
5 Correct 4 ms 11244 KB Output is correct
6 Correct 4 ms 11548 KB Output is correct
7 Correct 8 ms 11336 KB Output is correct
8 Correct 8 ms 11328 KB Output is correct
9 Correct 0 ms 11244 KB Output is correct
10 Correct 0 ms 11244 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 11244 KB Output is correct
2 Correct 148 ms 11244 KB Output is correct
3 Correct 172 ms 16268 KB Output is correct
4 Correct 148 ms 15956 KB Output is correct
5 Correct 160 ms 16272 KB Output is correct
6 Correct 116 ms 36896 KB Output is correct
7 Correct 168 ms 24008 KB Output is correct
8 Correct 104 ms 24012 KB Output is correct
9 Correct 152 ms 11244 KB Output is correct
10 Correct 132 ms 11244 KB Output is correct